Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Walking in the Rain

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn Berland the opposition is going to arrange mass walking on the boulevard. The boulevard consists of *n* tiles that are lain in a row and are numbered from 1 to *n* from right to left. The opposition should start walking on the tile number 1 and the finish on the tile number *n*. During the walk it is allowed to move from right to left between adjacent tiles in a row, and jump over a tile. More formally, if you are standing on the tile number *i* (*i* < *n* - 1), you can reach the tiles number *i* + 1 or the tile number *i* + 2 from it (if you stand on the tile number *n* - 1, you can only reach tile number *n*). We can assume that all the opposition movements occur instantaneously.

In order to thwart an opposition rally, the Berland bloody regime organized the rain. The tiles on the boulevard are of poor quality and they are rapidly destroyed in the rain. We know that the *i*-th tile is destroyed after *a*_{i} days of rain (on day *a*_{i} tile isn't destroyed yet, and on day *a*_{i} + 1 it is already destroyed). Of course, no one is allowed to walk on the destroyed tiles! So the walk of the opposition is considered thwarted, if either the tile number 1 is broken, or the tile number *n* is broken, or it is impossible to reach the tile number *n* from the tile number 1 if we can walk on undestroyed tiles.

The opposition wants to gather more supporters for their walk. Therefore, the more time they have to pack, the better. Help the opposition to calculate how much time they still have and tell us for how many days the walk from the tile number 1 to the tile number *n* will be possible.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{3}) — the boulevard's length in tiles.

The second line contains *n* space-separated integers *a*_{i} — the number of days after which the *i*-th tile gets destroyed (1 ≤ *a*_{i} ≤ 10^{3}).

Output

Print a single number — the sought number of days.

Examples

Input

4

10 3 5 10

Output

5

Input

5

10 2 8 3 5

Output

5

Note

In the first sample the second tile gets destroyed after day three, and the only path left is 1 → 3 → 4. After day five there is a two-tile gap between the first and the last tile, you can't jump over it.

In the second sample path 1 → 3 → 5 is available up to day five, inclusive. On day six the last tile is destroyed and the walk is thwarted.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2019 07:35:44 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|