package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  "container/heap"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}

type Evaluator func(a, b interface{}) interface{}
func Eval(a, b interface{}) interface{} {
  x := a.(int)
  y := b.(int)
  return MinInt(x, y)
} 
type SegmentTree struct {
  size  int
  data  []interface{}
  inf   interface{}
  eval  Evaluator
}
func InitSegmentTree(N int, inf interface{}, eval Evaluator) *SegmentTree {
  size := 1
  for size < N {
    size *= 2
  }
  S := make([]interface{}, size * 2)
  for i := range S {
    S[i] = inf
  }
  return &SegmentTree{
    size: size,
    data: S,
    inf:  inf,
    eval: eval,
  }
}
func CreateSegmentTree(A *[]interface{}, inf interface{}, eval Evaluator) *SegmentTree {
  N := len((*A))
  size := 1
  for size < N {
    size *= 2
  }
  S := make([]interface{}, size * 2)
  for i, a := range (*A) {
    S[size + i] = a
  }
  for i := N; i < size; i++ {
    S[size + i] = inf
  }
  for i := size - 1; i > 0; i-- {
    S[i] = eval(S[2 * i], S[2 * i + 1])
  }
  return &SegmentTree{
    size: size,
    data: S,
    inf:  inf,
    eval: eval,
  }
}
func (ST *SegmentTree) Update(index int, value interface{}) {
  idx := ST.size + index
  ST.data[idx] = value
  for idx > 1 {
    parent := idx / 2
    ST.data[parent] = ST.eval(ST.data[2 * parent], ST.data[2 * parent + 1])
    idx = parent
  }
}
func (ST *SegmentTree) Get(from, to, index, left, right int) interface{} {
  // get [from, to)
  if to <= left || right <= from { return ST.inf }
  if from <= left && right <= to { return ST.data[index] }
  m := (left + right) / 2
  lval := ST.Get(from, to, 2 * index, left, m)
  rval := ST.Get(from, to, 2 * index + 1, m, right)
  return ST.eval(lval, rval)
}
func (ST *SegmentTree) Query(from, to int) interface{} {
  return ST.Get(from, to, 1, 0, ST.size)
}
type Item struct {
  Priority int
  Entry interface{}
}

type Heap []*Item
func (H Heap) Len() int { return len(H) }
func (H Heap) Less(i, j int) bool { return H[i].Priority < H[j].Priority }
func (H Heap) Swap(i, j int) { H[i], H[j] = H[j], H[i] }
func (H *Heap) Pop() interface{} {
  Old := *H
  n := len(Old)
  item := Old[n - 1]
  *H = Old[0:n - 1]
  return item
}
func (H *Heap) Push(x interface{}) {
  item := x.(*Item)
  *H = append(*H, item)
}
type PriorityQueue struct {
  Comparator func(e interface{}) int
  Items Heap
}
func (PQ *PriorityQueue) Push(e interface{}) {
  item := Item{PQ.Comparator(e), e}
  heap.Push(&PQ.Items, &item)
}
func (PQ *PriorityQueue) Pop() interface{} {
  return heap.Pop(&PQ.Items).(*Item).Entry
}
func InitPQ(F func(interface{}) int) PriorityQueue {
  var H Heap
  return PriorityQueue{F, H}
}

func Solve() {
  var N int
  NextInt(&N)
  var P []int
  NextIntVec(&P)
  M := make([]int, N + 1)
  for i, p := range P {
    M[p] = i
  }
  Q := make([]int, 0)
  ST := make([]*SegmentTree, 2)
  for i := range ST {
    ST[i] = InitSegmentTree(N + 1, N + 1, Eval)
  }
  for i, p := range P {
    ST[i % 2].Update(i, p)
  }
  F := func(e interface{}) int { return e.([]int)[0] }
  PQ := InitPQ(F)
  p := ST[0].Query(0, N).(int)
  q := ST[1].Query(M[p] + 1, N).(int)
  PQ.Push([]int{p, q, 0, N, 0})
  for 0 < PQ.Items.Len() {
    pq := PQ.Pop().([]int)
    Q = append(Q, pq[0], pq[1])
    if pq[2] < M[pq[0]] {
      p = ST[pq[4]].Query(pq[2], M[pq[0]]).(int)
      q = ST[1 - pq[4]].Query(M[p], M[pq[0]]).(int)
      PQ.Push([]int{p, q, pq[2], M[pq[0]], pq[4]})
    }
    if 1 < M[pq[1]] - M[pq[0]] {
      p = ST[1 - pq[4]].Query(M[pq[0]], M[pq[1]]).(int)
      q = ST[pq[4]].Query(M[p], M[pq[1]]).(int)
      PQ.Push([]int{p, q, M[pq[0]] + 1, M[pq[1]], 1 - pq[4]})
    }
    if 1 < pq[3] - M[pq[1]] {
      p = ST[pq[4]].Query(M[pq[1]], pq[3]).(int)
      q = ST[1 - pq[4]].Query(M[p], pq[3]).(int)
      PQ.Push([]int{p, q, M[pq[1]] + 1, pq[3], pq[4]})
    }
  }
  WriteIntVec(Q)
  return
}

func main() {
  Solve()
  Output()
}

Measured memory_bytes: 69632