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.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 Composite {
	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);

		anc = new int[2 * n];
		full = new boolean[2 * n];
		rank = new int[2 * n];

		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(2 * n);
		for (int i = 0; i < n; i++) {
			if (b[2 * i] > h)
				return false;
			if (b[2 * i + 1] > h) {
				if (!merge(b[2 * i], b[2 * i])) {
					return false;
				}
			} else {
				if (!merge(b[2 * i], b[2 * i + 1])) {
					return false;
				}
			}
		}
		return true;
	}

	int[] stack = new int[2_000_001];

	void DJSet(int n) {
		Arrays.fill(anc, -1);
		Arrays.fill(full, false);
		Arrays.fill(rank, 0);
	}

	int[] anc;
	boolean[] full;
	int[] rank;

	boolean merge(int a, int b) {
		int aRoot = fRoot(a);
		int bRoot = fRoot(b);

		if (aRoot == bRoot) {
			if (full[aRoot]) {
				return false;
			}
			full[aRoot] = true;
			return true;
		}

		if (full[aRoot] && full[bRoot]) {
			return false;
		}

		if (rank[a] < rank[b]) {
			anc[aRoot] = bRoot;
			full[bRoot] = full[aRoot] || full[bRoot];
		} else {
			if (rank[a] == rank[b]) {
				anc[aRoot] = bRoot;
				rank[bRoot]++;
				full[bRoot] = full[aRoot] || full[bRoot];
			} else {
				anc[bRoot] = aRoot;
				full[aRoot] = full[aRoot] || full[bRoot];
			}
		}
		return true;
	}

	int fRoot(int cur) {
		int sSize = 0;
		while (anc[cur] != -1) {
			stack[sSize++] = cur;
			cur = anc[cur];
		}
		
		for(int i = 0; i < sSize; i++) {
			anc[stack[i]] = cur;
		}
		return cur;
	}

	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 Composite().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();
		}
	}
}