이 문제는 인터랙티브 문제입니다.

$\{1, 2, \dots, n\}$의 숨겨진 순열 $p_1, p_2, \dots, p_n$이 있습니다. 당신은 $p_l, \dots, p_r$의 반전(inversion) 수의 홀짝성을 질문하여 이 순열을 찾아야 합니다.

"? l r" 형식으로 질문할 수 있으며, 인터랙터는 $(\sum_{l \le i < j \le r} [p_i > p_j]) \pmod 2$를 응답합니다. 여기서 $[p_i > p_j]$는 $p_i > p_j$일 때 1, $p_i \le p_j$일 때 0입니다.

인터랙션 프로토콜

먼저 정수 $n$ ($1 \le n \le 2000$)을 읽어야 합니다.

그 후, 최대 $4 \times 10^4$번까지 질문할 수 있습니다. 질문하려면 "? l r" ($1 \le l \le r \le n$)을 별도의 줄에 출력한 다음, 표준 입력으로부터 응답을 읽어야 합니다.

답을 제출하려면 "! $p_1$ $p_2$ $\dots$ $p_n$"을 별도의 줄에 출력하십시오. 답을 출력하는 것은 $4 \times 10^4$번의 질문 횟수 제한에 포함되지 않습니다.

그 후, 프로그램은 종료되어야 합니다.

질문을 출력한 후에는 반드시 줄 바꿈을 출력하고 출력을 비워야(flush) 합니다. C++에서는 fflush(stdout) 또는 cout.flush(), Java에서는 System.out.flush(), Pascal에서는 flush(output), Python에서는 stdout.flush()를 사용하여 수행할 수 있습니다.

순열은 미리 고정되어 있음이 보장됩니다.

예제

입력 1

3
0
0
1

출력 1

? 1 2
? 1 3
? 2 3
! 2 3 1