거듭제곱의 거듭제곱

시간 제한2초메모리 제한512 MB

요약

N개의 정수를 재배열해 거듭제곱 탑 B1^(B2^(...^BN))의 값이 최대가 되게 하고, 최대를 이루는 순서 중 사전순으로 가장 앞선 배열을 출력합니다.

난이도: 보통10점 중 6점
유형: 그리디, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

ICPC에서 좋은 성적을 거두려면 수련이 빠질 수 없다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수련하기로 했다.

오늘의 수련은 아주 큰 수를 계산해서 계산력을 기르고 의식을 높이는 것이다. 큰 수가 쉽게 나오는 연산으로는 거듭제곱이 있다.

$N$ 개의 음이 아닌 정수 $A_1, A_2, \ldots, A_N$ 이 있다. 이들을 재배열한 $B_1, B_2, \ldots, B_N$ 가운데 $B_1^{B_2^{\cdots^{B_{N-1}^{B_N}}}}$ 의 값이 최대가 되는 것을 구하라. 토끼들에게는 당연한 이야기지만, 이 계산은 오른쪽 위에서부터 차례로 수행한다. 또한 $0^0 = 1$ 로 약속한다.

최대 조건을 만족하는 재배열이 여러 개라면, 그중 사전순으로 가장 작은 수열을 고른다.

입력

N
A1
...
AN

$1 \le N \le 100$ , $0 \le A_i \le 1{,}000{,}000{,}000$ 을 만족한다.

출력

출력은 $N$ 개의 줄로 이루어진다. $i$ 번째 줄에 $B_i$ 를 출력한다.

예제2

예제 1
입력
```
4
7
5
10
6
```
예상 출력
```
5
6
7
10
```
예제 2
입력
```
3
0
0
1000000000
```
예상 출력
```
1000000000
0
0
```