#include #include using namespace std; int op(int lhs, int rhs){return max(lhs, rhs);} constexpr int e(){return 0;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector> b(n, make_pair(1 << 30, 1 << 30)); atcoder::segtree seg(n); for(int i = 0, v; i < n; i++){ cin >> v, v--; int v2 = seg.prod(0, v); auto &&[x, y] = b[v2]; x = min(x, i + 1); y = min(y, v + 1); seg.set(v, v2 + 1); } for(auto &&[x, y] : b){ if(x >> 30) break; cout << x << ' ' << y << '\n'; } }