A. Shandom Ruffle

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

struct Treap {
   int val, pr, size;
   Treap *l, *r;

   Treap(): val(0), pr(0), size(0), l(nullptr), r(nullptr) { }
   Treap(int _val): val(_val), size(1), l(nullptr), r(nullptr) {
      static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      pr = int(rng());
   }
};

ostream &operator<<(ostream &out, Treap *t) {
   function<void(Treap*)> dfs = [&](Treap *t) {
      if (!t) return;
      dfs(t->l);
      out << t->val << ' ';
      dfs(t->r);
   };
   dfs(t);
   return out;
}

int size(Treap *a) { return a ? a->size : 0; }

Treap *treap_update(Treap *a) {
   if (!a) return nullptr;
   a->size = size(a->l) + size(a->r) + 1;
   return a;
}

Treap *join(Treap *a, Treap *b) {
   if (!a || !b) return a ? a : b;
   if (a->pr > b->pr) return a->r = join(a->r, b), treap_update(a);
   return b->l = join(a, b->l), treap_update(b);
}

Treap *join(vector<Treap*> treaps) {
   if (treaps.empty()) return nullptr;
   Treap *ret = treaps[0];
   for (int i = 1; i < sz(treaps); i++)
      ret = join(ret, treaps[i]);
   return ret;
}

pair<Treap*, Treap*> split(Treap *a, int pos) {
   if (!a) return { nullptr, nullptr };
   if (size(a->l) + 1 <= pos) {
      auto [ l, r ] = split(a->r, pos - size(a->l) - 1);
      a->r = l;
      return { treap_update(a), r };
   }
   auto [ l, r ] = split(a->l, pos);
   a->l = r;
   return { l, treap_update(a) };
}

void swap_segments(Treap *treap, int l1, int r1, int l2, int r2) {
   auto [ left1, suff1 ] = split(treap, l1 - 1);
   auto [ mid1, right1 ] = split(suff1, r1 - l1 + 1);
   auto [ left2, suff2 ] = split(right1, l2 - r1 - 1);
   auto [ mid2, right2 ] = split(suff2, r2 - l2 + 1);

   join({ left1, mid2, left2, mid1, right2 });
}

void solve() {
   int n;
   cin >> n;

   Treap *treap = new Treap(1);
   for (int i = 2; i <= n; i++)
      treap = join(treap, new Treap(i));

   for (int i = 1, a, b; i <= n; i++) {
      cin >> a >> b;
      if (a >= b) continue;
      int len = min(b - a, n - b + 1);
      swap_segments(treap, a, a + len - 1, b, b + len - 1);
   }

   cout << treap << endl;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   solve();

   return 0;
}