use proconio::input;
use ac_library::Segtree;
use ac_library::Max;

fn main(){
    input!{
        n: usize,
        p: [usize; n],
    }

    let mut seg = Segtree::<Max<usize>>::new(n);
    let mut d = vec![0; n];
    for i in 0..n{
        let x = p[i]-1;
        let mx = seg.prod(0..x);
        d[i] = mx+1;
        seg.set(x, d[i]);
    }

    let mut x = vec![n+1; n+1];
    let mut y = vec![n+1; n+1];
    for i in 0..n{
        x[d[i]] = x[d[i]].min(i+1);
        y[d[i]] = y[d[i]].min(p[i]);
    }

    for i in 1..=n{
        if x[i] != n+1{
            println!("{} {}", x[i], y[i]);
        }
    }
}