//---------- begin SegmentTree Point update Range query ----------
pub trait PURQ {
    type T: Clone;
    fn fold(l: &Self::T, r: &Self::T) -> Self::T;
    fn e() -> Self::T;
}

struct SegmentTreePURQ<R: PURQ> {
    seg: Vec<R::T>,
    size: usize,
}

#[allow(dead_code)]
impl<R: PURQ> SegmentTreePURQ<R> {
    fn new(n: usize) -> SegmentTreePURQ<R> {
        let size = n.next_power_of_two();
        SegmentTreePURQ {
            seg: vec![R::e(); 2 * size],
            size: size,
        }
    }
    fn build_by(a: &[R::T]) -> SegmentTreePURQ<R> {
        let size = a.len().next_power_of_two();
        let mut b = vec![R::e(); 2 * size];
        for i in 0..a.len() {
            b[i + size] = a[i].clone();
        }
        let mut seg = SegmentTreePURQ {
            seg: b,
            size: size,
        };
        seg.update_all();
        seg
    }
    fn update(&mut self, x: usize, v: R::T) {
        let mut x = x + self.size;
        let a = &mut self.seg;
        a[x] = v;
        x >>= 1;
        while x > 0 {
            a[x] = R::fold(&a[2 * x], &a[2 * x + 1]);
            x >>= 1;
        }
    }
    fn update_tmp(&mut self, x: usize, v: R::T) {
        self.seg[self.size + x] = v;
    }
    fn update_all(&mut self) {
        let a = &mut self.seg;
        for i in (1..self.size).rev() {
            a[i] = R::fold(&a[2 * i], &a[2 * i + 1]);
        }
    }
    fn find(&self, l: usize, r: usize) -> R::T {
        let mut x = R::e();
        let mut y = R::e();
        let mut l = l + self.size;
        let mut r = r + self.size;
        let a = &self.seg;
        while l < r {
            if l & 1 == 1 {
                x = R::fold(&x, &a[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = R::fold(&a[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        R::fold(&x, &y)
    }
}
//---------- end SegmentTree Point update Range query ----------

use proconio::*;
use std::cmp::*;

struct RMQ;
impl PURQ for RMQ {
    type T = (u32, usize);
    fn fold(l: &Self::T, r: &Self::T) -> Self::T {
        std::cmp::min(*l, *r)
    }
    fn e() -> Self::T {
        (std::u32::MAX, std::usize::MAX)
    }
}

#[fastout]
fn run() {
    input! {
        n: usize,
        p: [u32; n],
    }
    let mut seg = (0..2).map(|_| SegmentTreePURQ::<RMQ>::new(n)).collect::<Vec<_>>();
    for (i, p) in p.iter().enumerate() {
        seg[i & 1].update_tmp(i, (*p, i));
    }
    seg.iter_mut().for_each(|s| s.update_all());
    let find = |l: usize, r: usize| -> (u32, u32, usize, usize, usize, usize) {
        assert!(l + 2 <= r);
        let (a, x) = seg[l & 1].find(l, r);
        let (b, y) = seg[(l & 1) ^ 1].find(x, r);
        (a, b, l, r, x, y)
    };
    let mut h = std::collections::BinaryHeap::new();
    h.push(Reverse(find(0, n)));
    let mut ans = vec![];
    while let Some(Reverse((a, b, l, r, x, y))) = h.pop() {
        ans.push(a);
        ans.push(b);
        if l + 2 <= x {
            h.push(Reverse(find(l, x)));
        }
        if x + 1 + 2 <= y {
            h.push(Reverse(find(x + 1, y)));
        }
        if y + 1 + 2 <= r {
            h.push(Reverse(find(y + 1, r)));
        }
    }
    let mut s = String::new();
    for a in ans {
        s.push_str(&format!("{} ", a));
    }
    s.pop();
    println!("{}", s);
}

fn main() {
    run();
}


Measured memory_bytes: 23976