use std::cmp;
use std::collections::BinaryHeap;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let p: Vec<i64> = sc.vec(n);

    let mut odd = vec![];
    let mut even = vec![];
    for i in 0..n {
        if i % 2 == 0 {
            even.push((p[i], i));
            odd.push((1 << 50, i));
        } else {
            odd.push((p[i], i));
            even.push((1 << 50, i));
        }
    }

    let odd_table = sparse_table::SparseTable::from(&odd, (1 << 50, n), cmp::min);
    let even_table = sparse_table::SparseTable::from(&even, (1 << 50, n), cmp::min);

    let mut ans = vec![];
    let mut heap = BinaryHeap::new();
    heap.push((0, 0, n, false));
    while let Some((_, from, to, swap)) = heap.pop() {
        let (even, odd) = if swap {
            (&odd_table, &even_table)
        } else {
            (&even_table, &odd_table)
        };

        let (l, left) = even.get(from, to);
        let (r, right) = odd.get(left + 1, to);
        ans.push(l);
        ans.push(r);

        if from < left {
            let (l, _) = even.get(from, left);
            heap.push((-l, from, left, swap));
        }
        if left + 1 < right {
            let (l, _) = odd.get(left + 1, right);
            heap.push((-l, left + 1, right, !swap));
        }
        if right + 1 < to {
            let (l, _) = even.get(right + 1, to);
            heap.push((-l, right + 1, to, swap));
        }
    }

    for i in 0..n {
        if i > 0 {
            sc.write(" ");
        }
        sc.write(ans[i].to_string());
    }
    sc.write("\n");
}

pub mod sparse_table {

    pub struct SparseTable<T, F> {
        data: Vec<Vec<T>>,
        op: F,
    }

    impl<T, F> SparseTable<T, F>
    where
        T: Copy,
        F: Fn(T, T) -> T,
    {
        pub fn from(v: &[T], init: T, op: F) -> SparseTable<T, F> {
            let size = v.len().next_power_of_two();
            let count = size.trailing_zeros() as usize + 1;
            let mut data = vec![vec![init; size]; count];
            for (i, v) in v.iter().cloned().enumerate() {
                data[0][i] = v;
            }
            for c in 1..count {
                for i in 0..size {
                    let next = ::std::cmp::min(size - 1, i + (1 << (c - 1)));
                    data[c][i] = op(data[c - 1][i], data[c - 1][next]);
                }
            }

            SparseTable { data: data, op: op }
        }

        /// get the result for [l, r)
        pub fn get(&self, l: usize, r: usize) -> T {
            assert!(l < r);
            let length = r - l;
            if length == 1 {
                return self.data[0][l];
            }
            let block_size = length.next_power_of_two() >> 1;
            let c = block_size.trailing_zeros() as usize;
            let left = self.data[c][l];
            let right = self.data[c][r - block_size];
            (self.op)(left, right)
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 179024