#include using namespace std; #include using namespace atcoder; int op(int a, int b) { return max(a, b); } int e() { return -1; } int main () { int N; cin >> N; segtree sg(N); std::vector lv(N), A(N); for (int i = 0; i < N; i ++) { int a; cin >> a; a --; A[i] = a; lv[i] = sg.prod(0, a) + 1; sg.set(a, lv[i]); } int siz = *max_element(lv.begin(), lv.end()) + 1; vector mx(siz, N + 100), my(siz, N + 100); for (int i = 0; i < N; i ++) { int l = lv[i]; mx[l] = min(mx[l], i+1); my[l] = min(my[l], A[i]+1); } for (int i = 0; i < siz; i ++) { printf("%d %d\n", mx[i], my[i]); } cout << flush; }