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>
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 2e6 + 100;
const long long mod = 1e9 + 7;
const long double PI = acos((long double)-1);
long long pw(long long a, long long b, long long md = mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res = (a * res) % md;
    }
    a = (a * a) % md;
    b >>= 1;
  }
  return (res);
}
int n;
int a[maxn];
int b[maxn];
int A[maxn], B[maxn];
bitset<maxn> mark;
bitset<maxn> Mark;
int par[maxn], sz[maxn];
int d[maxn];
int getpar(int v) { return ((v == par[v]) ? v : par[v] = getpar(par[v])); }
vector<pair<int, int> > adj[maxn];
vector<int> vec;
int comp(int x) {
  return (lower_bound(vec.begin(), vec.end(), x) - vec.begin());
}
void merge(int v, int u) {
  v = getpar(v), u = getpar(u);
  d[v]++;
  if (v == u) return;
  if (sz[v] < sz[u]) swap(u, v);
  sz[v] += sz[u];
  d[v] += d[u];
  par[u] = v;
}
bool dfs(int v, int x) {
  if (mark[v]) return (1);
  mark[v] = 1;
  bool ok = 1;
  if (!Mark[A[v]] and a[v] <= x) {
    Mark[A[v]] = 1;
    for (auto [u, w] : adj[A[v]]) {
      ok &= dfs(w, x);
      if (!ok) return (0);
    }
    return (ok);
  } else if (!Mark[B[v]] and b[v] <= x) {
    Mark[B[v]] = 1;
    for (auto [u, w] : adj[B[v]]) {
      ok &= dfs(w, x);
      if (!ok) return (0);
    }
    return (ok);
  }
  return (0);
}
bool solve(int x) {
  x = vec[x - 1];
  Mark = mark = 0;
  memset(d, 0, sizeof d);
  bool ok = 1;
  for (int i = 0; i < n; i++)
    if (!mark[i]) {
      if (a[i] <= x and b[i] <= x)
        continue;
      else {
        ok &= dfs(i, x);
        if (!ok) return (0);
      }
    }
  for (int i = 0; i < vec.size(); i++) {
    sz[i] = 1, par[i] = i;
  }
  for (int i = 0; i < n; i++)
    if (!mark[i]) merge(A[i], B[i]);
  for (int i = 0; i < n; i++) {
    if (!mark[i] and d[getpar(A[i])] > sz[getpar(A[i])]) return (0);
  }
  return (ok);
}
void add(int u, int v, int w) {
  adj[u].push_back({v, w});
  adj[v].push_back({u, w});
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i] >> b[i], vec.push_back(a[i]), vec.push_back(i[b]);
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  int l = 0, r = vec.size();
  for (int i = 0; i < n; i++) A[i] = comp(a[i]), B[i] = comp(b[i]);
  for (int i = 0; i < n; i++) {
    add(A[i], B[i], i);
  }
  if (!solve(r)) cout << -1, exit(0);
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (solve(mid))
      r = mid;
    else
      l = mid;
  }
  cout << vec[r - 1];
  return (0);
}
