Polycarp studies in Berland State University. Soon he will have to take his exam. He has to pass exactly n exams.

For the each exam i there are known two days: a_i — day of the first opportunity to pass the exam, b_i — day of the second opportunity to pass the exam (a_i < b_i). Polycarp can pass at most one exam during each day. For each exam Polycarp chooses by himself which day he will pass this exam. He has to pass all the n exams.

Polycarp wants to pass all the exams as soon as possible. Print the minimum index of day by which Polycarp can pass all the n exams, or print -1 if he cannot pass all the exams at all.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 10^6) — the number of exams.

The next n lines contain two integers each: a_i and b_i (1 ≤ a_i < b_i ≤ 10^9), where a_i is the number of day of the first passing the i-th exam and b_i is the number of day of the second passing the i-th exam.

Output

If Polycarp cannot pass all the n exams, print -1. Otherwise print the minimum index of day by which Polycarp can do that.

Examples

Input

2
1 5
1 7


Output

5


Input

3
5 13
1 5
1 7


Output

7


Input

3
10 40
40 80
10 80


Output

80


Input

3
99 100
99 100
99 100


Output

-1
//created by Whiplash99
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class F
{
    static class DSU
    {
        int parent[], vertices[], edges[], max[], nextMax[];
        DSU(int N)
        {
            nextMax=new int[N];
            parent=new int[N]; max=new int[N];
            vertices =new int[N]; edges=new int[N];
            for(int i=0;i<N;i++) make_set(i);
        }
        void make_set(int v)
        {
            parent[v]=v; max[v]=v; nextMax[v]=0;
            vertices[v]=1; edges[v]=0;
        }
        int find_set(int v)
        {
            if(v==parent[v])
                return v;
            return parent[v]=find_set(parent[v]);
        }
        void union_sets(int a, int b)
        {
            a=find_set(a);
            b=find_set(b);

            if(vertices[a]< vertices[b])
            {
                int tmp=a;
                a=b;
                b=tmp;
            }

            edges[a]++;
            if(a==b) return;

            parent[b]=a;
            vertices[a]+= vertices[b]; edges[a]+=edges[b];
            int tmp=Math.max(max[a], max[b]), tmp2=Math.min(max[a], max[b]);
            int tmp3=Math.max(nextMax[a], nextMax[b]);
            max[a]=tmp; nextMax[a]=Math.max(tmp2,tmp3);
        }
    }
    public static void main(String[] args) throws IOException
    {
        Reader r=new Reader();

        int i,N;

        N=r.nextInt();
        int[] a=new int[N];
        int[] b=new int[N];
        Integer[] c=new Integer[2*N];
        int[] inv=new int[2*N+5];

        for(i=0;i<N;i++)
        {
            a[i]=r.nextInt();
            b[i]=r.nextInt();
            c[i*2]=a[i];
            c[i*2+1]=b[i];
        }

        Arrays.sort(c);
        HashMap<Integer,Integer> map=new HashMap<>();
        int k=0;
        for(i=0;i<2*N;i++)
        {
            if(i>0&&c[i].equals(c[i-1])) continue;
            inv[k]=c[i];map.put(c[i],k++);
        }

        DSU dsu=new DSU(2*N+5);
        for(i=0;i<N;i++) dsu.union_sets(map.get(a[i]),map.get(b[i]));

        int max=0;
        for(i=0;i<k;i++)
        {
            if(dsu.find_set(i)!=i) continue;
            if(dsu.edges[i]>dsu.vertices[i])
            {
                max=-1;
                break;
            }
            if(dsu.edges[i]==dsu.vertices[i]) max=Math.max(max,dsu.max[i]);
            else if(dsu.edges[i]==dsu.vertices[i]-1) max=Math.max(max,dsu.nextMax[i]);
        }
        if(max==-1) System.out.println(max);
        else System.out.println(inv[max]);
    }
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
        public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
        }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
        }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
        }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
        }public void close() throws IOException{if(din==null) return;din.close();}
    }
}