After millennia of lurking in the shadows, the Sith have revealed their insidious presence! Jedi Master Qui-Gon Jinn and his padawan Obi-Wan Kenobi were culling droids in the Battle of Naboo's final moments when the Sith Lord Darth Maul ambushed them. Maul lures the pair into the heart of the Theed power generator, an unfathomably deep plasma well dotted with narrow bridges over colossal drops. Here, their fated duel will unfold.
Amid the chaos, Obi-Wan is kicked off the highest bridge all the way to the very bottom of the well. Obi-Wan must now make his way back to the top as soon as possible to rejoin the fight! There are $$$n$$$ bridges each of varying heights $$$h_1, h_2, ... , h_{n-1}, h_n$$$, and the bridge Obi-Wan must return to is of height $$$h_n$$$.
Luckily, Obi-Wan is a highly skilled Jedi apprentice. If a Jedi has strength $$$s$$$, then they are able to jump a height of $$$s$$$ units, meaning that Obi-Wan can jump to any higher bridge if the height difference is less than or equal to $$$s$$$. A Jedi's jump strength $$$s$$$ doesn't change between jumps.
Obi-Wan wants to conserve as much strength as he can to help defeat Darth Maul, so he needs to minimize the strength he allocates to jumping. Help Obi-Wan determine the minimum strength $$$s$$$ he needs to return to the highest bridge. His initial height is at $$$0$$$ units. All of the bridges' heights are in non-decreasing order, with $$$h_n$$$ being the highest.
The first line contains a single integer $$$n \: (1 \leq n \leq 100)$$$ — the number of bridges.
The second line contains $$$n$$$ integers $$$h_1, h_2, ... , h_{n-1}, h_n \: (1 \leq h_i \leq h_{i+1} \leq 1000)$$$ — the height of each bridge in non-decreasing order.
Output a single integer — the minimum strength $$$s$$$ needed to be able to make it to the $$$n$$$th bridge.
310 20 40
20
51 1 2 2 2
1
510 10 10 10 10
10
In the first test case, strength $$$20$$$ is sufficient to make it to the 3rd bridge. A possible path for Obi-Wan could be:
$$$0 \rightarrow 20 \rightarrow 40$$$. He needs strength $$$20$$$ to make both of the jumps.
In the second test case, strength $$$1$$$ is sufficient to make it to the fifth bridge. A possible path for Obi-Wan could be:
$$$0 \rightarrow 1 \rightarrow 2$$$.
He needs strength $$$1$$$ to make both of the jumps. Note that Obi-Wan needs strength $$$0$$$ to jump across bridges of the same height, so he can just jump to any bridge of height 2 and then make it to bridge $$$n$$$ from there.
In the third test case, strength $$$10$$$ is sufficient to make it to the first bridge. It is clear to see that he doesn't need more to jump from the first bridge to the fifth bridge.
