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
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

// resubmission of uwi's solution to see if it runs in time

public class F {
	InputStream is;
	PrintWriter out;
	String INPUT = "";

	void solve() {
		int n = ni();
		int[] a = na(2 * n);
		int[] b = Arrays.copyOf(a, 2 * n);
		int[] imap = shrinkX(b);
		if (!ok(imap.length - 1, b)) {
			out.println(-1);
			return;
		}
		int low = -1, high = imap.length;
		while (high - low > 1) {
			int h = high + low >> 1;
			if (ok(h, b)) {
				high = h;
			} else {
				low = h;
			}
		}
		out.println(imap[high]);
	}

	boolean ok(int h, int[] b) {
		int n = b.length / 2;
		DJSet ds = new DJSet(2 * n);
		for (int i = 0; i < n; i++) {
			if (b[2 * i] > h)
				return false;
			if (b[2 * i + 1] > h) {
				if (++ds.cycle[ds.root(b[2 * i])] >= 2)
					return false;
			} else {
				if (ds.union(b[2 * i], b[2 * i + 1])) {
					if (++ds.cycle[ds.root(b[2 * i])] >= 2)
						return false;
				} else {
					if (ds.cycle[ds.root(b[2 * i])] >= 2)
						return false;
				}
			}
		}
		return true;
	}

	public static class DJSet {
		public int[] upper;
		public int[] cycle;

		public DJSet(int n) {
			upper = new int[n];
			Arrays.fill(upper, -1);
			cycle = new int[n];
		}

		public int root(int x) {
			return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
		}

		public boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		public boolean union(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (upper[y] < upper[x]) {
					int d = x;
					x = y;
					y = d;
				}
				upper[x] += upper[y];
				upper[y] = x;

				cycle[x] += cycle[y];
			}
			return x == y;
		}

		public int count() {
			int ct = 0;
			for (int u : upper)
				if (u < 0)
					ct++;
			return ct;
		}
	}

	public static int[] shrinkX(int[] a) {
		int n = a.length;
		long[] b = new long[n];
		for (int i = 0; i < n; i++)
			b[i] = (long) a[i] << 32 | i;
		Arrays.sort(b);
		int[] ret = new int[n];
		int p = 0;
		ret[0] = (int) (b[0] >> 32);
		for (int i = 0; i < n; i++) {
			if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0) {
				p++;
				ret[p] = (int) (b[i] >> 32);
			}
			a[(int) b[i]] = p;
		}
		return Arrays.copyOf(ret, p + 1);
	}

	void run() throws Exception {
		is = System.in;
		out = new PrintWriter(System.out);

		solve();
		out.flush();
	}

	public static void main(String[] args) throws Exception {
		new F().run();
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
}