#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 1e5 + 10;

int a[N], pos[N];
pair<int, int > seg[N];

int ed, cnt_query;

int query (int i, int j) {
  ++cnt_query;
//  if (i >= j) exit(0);
  assert(i < j);
  #ifdef ngu
  if (--ed == 0) return -1;
  if (a[i] > a[j]) {
    swap(a[i], a[j]);
    return 1;
  }
  return 0;
  #else
  cout << i << " " << j << endl;
  int x; cin >> x;
  if (x == -1) exit(0);
  return x;
  #endif // ngu
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  #ifdef ngu
  cin >> ed;
  #endif // ngu

  int n; cin >> n;

  #ifdef ngu
  for(int i = 1; i <= n; i++) cin >> a[i];
  #endif // ngu

  int cnt = 1;
  seg[1] = make_pair(1, 1);

  for(int i = 1; i < n; i++) {
    if (query(i, i + 1) == 1) {
      if (seg[cnt].first == i) cnt--;
      else seg[cnt].second = i - 1;
      cnt++;
      seg[cnt] = make_pair(i, i + 1);
    }
    else seg[cnt].second = i + 1;
  }

  while (cnt > 1) {
    int cost = 1e9, nxt = 0;
    for(int i = 1; i < cnt; i++) {
      int tmp = seg[i].second - seg[i].first + seg[i + 1].second - seg[i + 1].first;
      if (cost > tmp) {
        cost = tmp;
        nxt = i;
      }
    }
    int i = seg[nxt].first;
    int j = seg[nxt + 1].first;
    for(int i = seg[nxt].first; i <= seg[nxt + 1].second; i++) pos[i] = i;

    auto find_pos = [&] (int x) {
      for(int k = seg[nxt].first; k <= seg[nxt + 1].second; k++) if (pos[k] == x) return k;
      return 0;
    };
    while (i <= seg[nxt].second || j <= seg[nxt + 1].second) {
      int posx = i <= seg[nxt].second ? find_pos(i) : 0;
      int posy = j <= seg[nxt + 1].second ? find_pos(j) : 0;
      int nxt_pos = i + j - seg[nxt + 1].first;
      if (posx > posy) swap(posx, posy);
      if (posx && posy) {
        if (query(posx, posy)) {
          swap(pos[posx], pos[posy]);
        }
      }
      else posx = max(posx, posy);

      if (pos[posx] == i && i <= seg[nxt].second) i++;
      else j++;

      if (posx != nxt_pos) {
        if (query(nxt_pos, posx) == 1) {
          swap(pos[nxt_pos], pos[posx]);
        }
      }
//      cout << i << " " << j << endl;
//      for(int i = 1; i <= n; i++) cerr << a[i] << " "; cerr << endl;
//      for(int i = 1; i <= n; i++) cerr << pos[i] << " "; cerr << endl;
    }


    seg[nxt].second = seg[nxt + 1].second;
    for(int i = nxt + 1; i <= cnt; i++) seg[i] = seg[i + 1];
    cnt--;
  }

  #ifdef ngu
  cout << cnt_query << endl;
  for(int i = 1; i <= n; i++) cout << a[i] << " ";
  for(int i = 2; i <= n; i++) assert(a[i] >= a[i - 1]);
  #endif // ngu
}