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;
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
using Array = vector<ll>;
using Matrix = vector<Array>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  ll to, cap, rev;
  Edge(ll _to, ll _cap, ll _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
void add_edge(vector<vector<Edge>> &G, ll from, ll to, ll cap, bool revFlag,
              ll revCap) {
  G[from].push_back(Edge(to, cap, (ll)G[to].size()));
  if (revFlag) G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}
class UnionFind {
  vector<int> data;
  int num;

 public:
  UnionFind(int size) : data(size, -1), num(size) {}
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
      num--;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  int numSet() { return num; }
};
void solve() {
  ll n;
  cin >> n;
  vec<ll> a(n), b(n);
  vec<ll> xs;
  for (ll i = (ll)(0); i < (ll)(n); ++i) {
    cin >> a[i] >> b[i];
    xs.push_back(a[i]);
    xs.push_back(b[i]);
  }
  sort((xs).begin(), (xs).end());
  xs.erase(unique((xs).begin(), (xs).end()), xs.end());
  int m = xs.size();
  UnionFind uni(m);
  vec<ll> num(m, 0);
  vec<ll> r1(m, 0);
  vec<ll> r2(m, 0);
  for (ll i = (ll)(0); i < (ll)(n); ++i) {
    auto aa = lower_bound((xs).begin(), (xs).end(), a[i]) - xs.begin();
    auto bb = lower_bound((xs).begin(), (xs).end(), b[i]) - xs.begin();
    int u = uni.root(aa);
    int v = uni.root(bb);
    if (u == v) {
      num[u]++;
    } else {
      uni.unionSet(u, v);
      int r = uni.root(u);
      num[r] = num[u] + num[v] + 1;
      ll ma = max(u, v);
      ll mi = min(u, v);
      auto update = [&](ll x) {
        if (ma < x) {
          mi = ma;
          ma = x;
        } else if (mi < x) {
          mi = x;
        }
      };
      update(r1[u]);
      update(r1[v]);
      update(r2[u]);
      update(r2[v]);
      r1[r] = ma;
      r2[r] = mi;
    }
  }
  ll ans = 0;
  for (ll i = (ll)(0); i < (ll)(m); ++i) {
    if (uni.root(i) != i) continue;
    if (num[i] > uni.size(i)) {
      cout << -1 << '\n';
      return;
    } else {
      int r = r1[i];
      if (num[i] < uni.size(i)) {
        r = r2[i];
      }
      chmax(ans, xs[r]);
    }
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
