There are $$$N$$$ sightseeing spots numbered from $$$1$$$ to $$$N$$$. The height of the $$$i$$$-th spot is $$$h_i$$$, and heights are strictly increasing. That is, $$$h_1 \lt h_2 \lt \ldots \lt h_N$$$.

Every pair of sightseeing spots is connected by a cable car, but to reduce costs, each cable car only runs from a lower spot to a higher one. That is, for every pair $$$i \lt j$$$, there is a cable car from spot $$$i$$$ to spot $$$j$$$, and it takes exactly $$$h_j - h_i$$$ units of time to travel.

However, when there are multiple cable cars departing from the same spot, you cannot freely choose which one to take. Specifically, from spot $$$i$$$, there are $$$N - i$$$ possible outgoing cable cars, going to spots $$$i+1, i+2, \ldots, N$$$. At time $$$t$$$, the only cable car available is the one going to spot $$$i + 1 + (t \bmod (N - i))$$$.

For example, if $$$N = 6$$$ and you are at spot 3, the available destination changes as follows:

• At time 0, the cable goes to spot 4.
• At time 1, it goes to spot 5.
• At time 2, it goes to spot 6.
• At time 3, it goes to spot 4 again, and so on.

You may choose to wait at a spot for any amount of time if the current destination is not the one you want.

You are currently at spot 1 and it is now time $$$T$$$. You want to travel to spot $$$N$$$ using the cable cars. What is the minimum amount of time needed to reach your destination? You may assume that switching cable cars takes no time.