#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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

Np_{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) |

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 23 | 2s | 256MB | Minimum |

2 | 0 | 3 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o youngmaids -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512