ordine

Gigel a primit de ziua lui un joc cu bile. Jocul conține $n$ bile numerotate cu numerele naturale distincte de la $1$ la $n$. Jucându-se, Gigel a amestecat bilele astfel încât acum ele nu mai sunt în ordine. Ca să le pună înapoi în cutia jocului, Gigel ia de pe masă bilele una câte una, și le pune în cutie formând un șir. Însă Gigel se joacă și acum, astfel încât el nu pune bilele la rând, una după alta, ci are o regulă pe care o respectă cu strictețe. Astfel, Gigel încearcă să plaseze fiecare bilă pe care a luat-o de pe masă exact la mijlocul șirului de bile deja format. Dacă acest lucru nu este posibil (șirul are lungime impară), atunci el plasează bila la sfârșitul șirului de bile deja format. După ce toate bilele au fost puse în cutie, Gigel își dă seama că nu a notat ordinea în care a luat bilele de pe masă și, în mod firesc, își pune problema dacă nu cumva poate deduce acest lucru din șirul de bile pe care tocmai l-a format.

Cerință

Cunoscându-se numărul de bile și configurația finală a bilelor în șir să se determine:

1. numărul ultimei bile luate de pe masă;
2. ordinea în care bilele au fost luate de pe masă.

Date de intrare

Fișierul de intrare ordine.in conține pe prima linie numărul $n$ de bile. Pe linia a doua a fișierului de intrare se găsesc $n$ numere naturale, cu valori între $1$ și $n$, separate prin câte un spațiu, care reprezintă șirul de bile obținut de Gigel în cutie. Linia a treia conține una dintre valorile $1$ sau $2$ reprezentând cerința $1$, dacă se cere determinarea ultimei bile luate de Gigel de pe masă, respectiv cerința $2$, dacă se cere determinarea ordinii în care Gigel a luat bilele de pe masă.

Date de ieșire

În fișierul de ieșire ordine.out va conține pe prima linie o valoarea naturală reprezentând numărul ultimei bile luate de Gigel, dacă cerința a fost $1$, respectiv $n$ numere naturale, cu valori cuprinse între $1$ și $n$, separate prin câte un spațiu, care reprezintă ordinea în care Gigel a luat bilele de pe masă, dacă cerința a fost $2$.

Restricții și precizări

• $1 \leq n \leq 250 \ 000$;
• Pentru cerința $1$ se acordă $30\%$ din punctaj, iar pentru cerința $2$ se acordă $70\%$ din punctaj.

Exemplul 1

ordine.in

7
1 7 2 5 3 4 6
1

ordine.out

5

Exemplul 2

ordine.in

7
1 7 2 5 3 4 6
2

ordine.out

1 3 7 4 2 6 5