### ** youngmaids**

### youngmaids

### Problem Statement

Let `N` be a positive even number.

We have a permutation of `(1, 2, ..., N)`, `p = (p`_{1}, p_{2}, ..., p_{N}).
Snuke is constructing another permutation of `(1, 2, ..., N)`, `q`, following the procedure below.

First, let `q` be an empty sequence.
Then, perform the following operation until `p` becomes empty:

- Select two adjacent elements in
`p`, and call them `x` and `y` in order. Remove `x` and `y` from `p` (reducing the length of `p` by `2`), and insert `x` and `y`, preserving the original order, at the beginning of `q`.

When `p` becomes empty, `q` will be a permutation of `(1, 2, ..., N)`.

Find the lexicographically smallest permutation that can be obtained as `q`.

### Constraints

`N` is an even number.
`2 ≤ N ≤ 2 × 10`^{5}
`p` is a permutation of `(1, 2, ..., N)`.

### Input

Input is given from Standard Input in the following format:

`N`
`p`_{1} `p`_{2} `...` `p`_{N}

### Output

Print the lexicographically smallest permutation, with spaces in between.

### Sample Input 1

4
3 2 4 1

### Sample Output 1

3 1 2 4

The solution above is obtained as follows:

`p` |
`q` |

`(3, 2, 4, 1)` |
`()` |

↓ |
↓ |

`(3, 1)` |
`(2, 4)` |

↓ |
↓ |

`()` |
`(3, 1, 2, 4)` |

### Sample Input 2

2
1 2

### Sample Output 2

1 2

### Sample Input 3

8
4 6 3 2 8 5 7 1

### Sample Output 3

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

`p` |
`q` |

`(4, 6, 3, 2, 8, 5, 7, 1)` |
`()` |

↓ |
↓ |

`(4, 6, 3, 2, 7, 1)` |
`(8, 5)` |

↓ |
↓ |

`(3, 2, 7, 1)` |
`(4, 6, 8, 5)` |

↓ |
↓ |

`(3, 1)` |
`(2, 7, 4, 6, 8, 5)` |

↓ |
↓ |

`()` |
`(3, 1, 2, 7, 4, 6, 8, 5)` |