In 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 ai days of rain (on day ai tile isn't destroyed yet, and on day ai + 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 ≤ 103) — the boulevard's length in tiles.

The second line contains n space-separated integers ai — the number of days after which the i-th tile gets destroyed (1 ≤ ai ≤ 103). 

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.
/* sup
 * lol not much
  alright let's have bad coding style and bad commenting style
 lol why would we want comments oh wait I see
  */
  
import java.util.*; //steven http://codeforces.com/problemset/problem/192/B
import java.io.*; // nick oh wait do we nto need this T_T w/e

public class Main { // steven, not sure if i'm doing my java right i forgot everything
  public static void main(String[] args) throws Exception { // nick do w/e just set up I/O
         BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); //steven i think a PQ is enough
        int n = Integer.parseInt(r.readLine()); // nick uh isn't this just some dumb DP?
        int ans = 0; /*steven actually just sort the tiles, and iterate. check if any adjacent was rained out for each. do we need some kind of pair*/
        StringTokenizer st = new StringTokenizer(r.readLine()); /* Nick uh yeah darn I can code that separately while you do the stuff*/
        pair ar[] = new pair[n]; //wait we need to do line by line though
    // Nick wait so like line N must always come before line N+1?
        //steven yeah no inserting :(
        for(int i = 0; i < n; i++) { // Nick okay fine tahs' okay
            int next = Integer.parseInt(st.nextToken()); //steven
            ar[i] = new pair(next, i); // Nick so first token is time and second token is index I think this is okay
        } //k, we need  now Pair extends pair loll also a boolean[] to mark when stuff is rained out
        boolean[] used = new boolean[n]; // Nick 
        Arrays.sort(ar); //i think this is right
        for(int i = 0; i < n; i++) { // Nick note to self pair must implement Comparable<pair>
            pair p = ar[i]; //steven we can have int fi and int se for pair.        
            used[p.fi] = true; // nick so like this? oh wait this is wrong it should be se lol we can just swap haha
            if (p.fi - 1 >= 0 && used[p.fi - 1] || (p.fi + 1 < n && used[p.fi + 1])) {//steven,  doesn't matter yeah
                System.out.println(p.se); // nick wait aren't you missing like p.fi == 0 or p.fi == n-1
                int what; //steven i have p.fi - 1 >= 0, is that wrong?
                // nick but like if the first or last tile is out then that also works
            } else if (p.fi == 0 || p.fi == n - 1) { // steven good catch i didn't read the problem
                System.out.println(p.se); /* nick also we need to be careful because we can't print multiple times so you might want to consider adding an else clause and then doing continue so we can break out at the right time */
            } else continue; //it's fine just end now wait we need to uh return here.
        return; // nick like this?
        } // i think so
   } // nick  
  static class pair implements Comparable<pair> { //steven
       public int fi, se; // nick
         public   int compareTo(pair o) { //steven also need constructor 
              return se - o.se; // nick
            } //steven
       public pair(int a, int b) { // nick so like we need to swap, so b to fi and 
            fi = b; //steven i think this is right
            se = a; // nick yeah 
       } //steven now Pair extends pair
    } // nick lol        
  // static class Pair extends pair { //steven this is ugly hm
    //   public Pair(int a, int b) { super(a,b); } // Nick
    //} //steven        
} // Nick gogo submit?
            //steven submittied we got it wrong
            //need public class my bad
            //compile error darn
            //lol woops br vs r :\
            //and static class ah
            //and public int compareTo darnnn
            //runtime error now
            //how do you do oop
            //lol uh idk but I don't understand what this class load error is hm what happens if we switch the case
// nick lol added