Ancient Castle Ruins

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

You stumble across the ruins of an ancient castle...

The ruins of the castle have left a strange pillar formation behind. In particular, there are N adjacent pillars each with height h_i. Let x represent your exhaustion. It initially starts at 1, and increases by 1 after each time you jump to a taller pillar. It takes x seconds to travel from pillar i to pillar i+1 if h_i \ge h_{i+1}. However, there are 2 different ways to travel to a taller pillar.

  1. You can run across pillar i in x seconds and then climb up to pillar i+1 in x(h_{i+1}-h_i) additional seconds.
  2. You can jump directly from pillar i to pillar i+1 in x seconds. You can jump as high as you want, but jumping will exhaust you.

Given this information, what is the lowest amount of time needed to get from pillar 1 to pillar N?


2 \le N \le 2 \times 10^5

1 \le h_i \le 10^9

Subtask 1 [40%]

2 \le N \le 2000

1 \le h_i \le 10^5

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line of input contains an integer N.

The second line of input contains N space separated integers representing h_i, the height of each pillar.

Output Specification

Output a single integer, the lowest achievable time in seconds.

Sample Input

6 2 1 2 3 9 2 3 7

Sample Output


Sample Input Visualized

Sample Input Visualized


There are no comments at the moment.