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

const INF: i64 = 1 << 50;
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 = sc.vec(n);
    let mut odd = vec![(INF, n); n];
    let mut even = vec![(INF, n); n];
    for i in 0..n {
        if i % 2 == 0 {
            even[i] = (p[i], i);
        } else {
            odd[i] = (p[i], i);
        }
    }

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

    let mut ans = vec![];
    let mut heap = BinaryHeap::new();
    heap.push((0, 0, n, false));
    while let Some((_, from, to, offset)) = heap.pop() {
        let (v, i, u, j) = if offset {
            let (v, i) = odd_table.get(from, to);
            let (u, j) = even_table.get(i, to);
            (v, i, u, j)
        } else {
            let (v, i) = even_table.get(from, to);
            let (u, j) = odd_table.get(i, to);
            (v, i, u, j)
        };

        ans.push(v);
        ans.push(u);

        if from < i {
            let (v, _) = if offset {
                odd_table.get(from, i)
            } else {
                even_table.get(from, i)
            };
            heap.push((-v, from, i, offset));
        }
        if i + 1 < j {
            let (v, _) = if !offset {
                odd_table.get(i + 1, j)
            } else {
                even_table.get(i + 1, j)
            };
            heap.push((-v, i + 1, j, !offset));
        }
        if j + 1 < to {
            let (v, _) = if offset {
                odd_table.get(j + 1, to)
            } else {
                even_table.get(j + 1, to)
            };
            heap.push((-v, j + 1, to, offset));
        }
    }

    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: 177660