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
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9 + 7;
const int N = 4e6 + 10;
const long long MOD = 998244353;
int readint() {
  int x = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x;
}
class UnionFind {
 public:
  int p[N];
  void init(int n = N) { memset(p, -1, sizeof(int) * n); }
  int treesize(int x) { return -p[Find(x)]; }
  int Find(int x) {
    int s = x;
    while (p[s] >= 0) s = p[s];
    while (x != s) {
      int t = p[x];
      p[x] = s;
      x = t;
    }
    return s;
  }
  void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);
    if (p[px] > p[py]) swap(px, py);
    p[px] += p[py];
    p[py] = px;
  }
} uf;
int pos[N];
int tot[N];
int deg[N];
vector<int> v[N];
int main() {
  int n = readint();
  uf.init();
  int k = 0;
  vector<pair<int, int>> vp;
  map<int, int> mc;
  for (int i = 0; i < n; i++) {
    int x = readint();
    int y = readint();
    if (!mc.count(x)) mc[x] = ++k;
    if (!mc.count(y)) mc[y] = ++k;
    pos[mc[x]] = x;
    pos[mc[y]] = y;
    x = mc[x];
    y = mc[y];
    vp.push_back({x, y});
    deg[x]++;
    deg[y]++;
    if (uf.Find(x) != uf.Find(y)) uf.Union(x, y);
  }
  for (auto &p : vp) {
    int x, y;
    tie(x, y) = p;
    tot[uf.Find(x)]++;
  }
  for (int i = 1; i <= k; i++) {
    if (uf.Find(i) != i) continue;
    if (tot[i] > uf.treesize(i)) {
      puts("-1");
      return 0;
    }
  }
  int ans = 0;
  for (int i = 1; i <= k; i++) {
    int p = uf.Find(i);
    if (tot[p] == uf.treesize(p)) {
      ans = max(ans, pos[i]);
    } else {
      v[p].push_back(pos[i]);
    }
  }
  for (int i = 1; i <= k; i++) {
    if (v[i].empty()) continue;
    sort(v[i].begin(), v[i].end());
    v[i].pop_back();
    ans = max(ans, v[i].back());
  }
  printf("%d\n", ans);
  return 0;
}
