실로폰

실로폰은 나무 막대를 쳐서 소리를 내는 악기이다. 막대 하나는 늘 같은 음높이로 울리므로, 실로폰은 서로 다른 음높이를 내는 막대들로 이루어진다. JOI 군은 막대가 $N$개인 실로폰을 샀다. 막대는 왼쪽에서 오른쪽으로 한 줄로 놓여 있고, 1번부터 $N$번까지 번호가 붙어 있다. $i$번 막대는 높이 $A_i$의 음을 낸다 ($1 \le A_i \le N$). 서로 다른 막대는 서로 다른 음높이를 낸다. 가장 낮은 음을 내는 막대의 번호는 가장 높은 음을 내는 막대의 번호보다 작다. JOI 군은 어느 막대가 어떤 음을 내는지 모르므로 각 막대의 음높이를 알아내려고 한다. 여러 막대를 동시에 치면 그중 가장 높은 음과 가장 낮은 음의 차이를 들을 수 있다. 정수 $s$, $t$ ($1 \le s \le t \le N$)에 대해 $s$번부터 $t$번까지의 막대를 함께 칠 수 있고, 그러면 $A_s, A_{s+1}, \ldots, A_t$의 최댓값과 최솟값의 차이를 알 수 있다. JOI 군은 10000번 안에 모든 막대의 음높이를 정해야 한다.

• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_i \ne A_j$ ($1 \le i < j \le N$)
• $A_i = 1$이고 $A_j = N$인 $i$, $j$에 대해 $i < j$이다.