$1$부터 $N$까지의 정수로 이루어진 순열 $A_1, A_2, \cdots, A_N$이 있다. 이 순열이 무엇인진 알 수 없지만, 아래의 쿼리를 통해 순열에 관한 정보를 얻을 수 있다.

• $\texttt{? l r}$ ($l \leq r$) : $l \leq i \leq r$을 만족하는 $i$에 대해 $A_i$의 최댓값과 최솟값의 차이를 알려준다.

최대 $2 \times N$번의 쿼리를 사용하여, 아래 Interaction에 명시된 조건을 만족하는 순열을 출력하여라.

여기서 순열이란, $1, 2, \cdots, N$이 정확히 한 번씩 사용된 수열을 의미한다. 예를 들어 $[1, 3, 2, 4]$는 순열이지만, $[1, 1, 3]$, $[1, 2, 4,5]$는 순열이 아니다.

인터랙션

첫 줄에 숨겨진 순열 $A_1, A_2, \cdots, A_N$의 길이 $N$이 주어진다. ($1 \leq N \leq 10,000$)

이후, 채점기에 쿼리를 보낼 수 있다. 쿼리는 다음과 같은 형식으로 한줄에 출력해야 하며, 최대 $2 \times N$번 보낼 수 있다.

$\texttt{? l r}$ ($1 \leq l \leq r \leq N$)

해당 쿼리를 출력한 이후, $A_l, A_{l+1}, \cdots, A_r$ 중 최댓값과 최솟값의 차이를 나타내는 정수 하나가 입력으로 주어진다.

이후 복원한 순열 $C_1, C_2, \cdots, C_N$을 출력할 때는 아래와 같은 형식으로 한 줄에 출력해야 한다.

$!$ $C_1$ $C_2$ $\cdots$ $C_N$

이때, 출력한 순열이 아래 두 조건 중 하나를 만족한다면 정답으로 처리된다.

• 모든 $1 \leq i \leq N$에 대해 $C_i = A_i$
• 모든 $1 \leq i \leq N$에 대해 $C_i = N+1-A_i$

각 쿼리를 출력한 뒤에는 반드시 표준 출력을 flush해야 한다.

예를 들어, 각 언어에서는 다음과 같이 할 수 있다.

• C: $\texttt{fflush(stdout);}$
• C++: $\texttt{cout << flush;}$ 또는 $\texttt{cout.flush();}$
• Python: $\texttt{sys.stdout.flush()}$ 또는 $\texttt{print(..., flush=True)}$
• Java: $\texttt{System.out.flush();}$

예제

예제 1

입력

4

3

2

3

출력

? 1 4

? 1 3

? 2 4

! 2 4 3 1