모든 구간 LIS

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

길이 $N$의 숨겨진 순열 $P = [P_1, P_2, \cdots, P_N]$이 있다.

$f(l,r)$를 연속한 부분수열 $P_l,P_{l+1},\cdots,P_r$의 가장 긴 증가하는 부분수열의 길이라고 정의한다. 증가하는 부분수열에서 원소의 값은 엄격하게 증가해야 한다.

당신은 인터랙터에게 구간을 질의하여 해당 구간의 $f(l,r)$를 알 수 있다. 최대 $600$번의 질의를 사용하여 모든 $1 \leq l \leq r \leq N$에 대한 $$를 구하여라.

처음에 참가자의 프로그램은 정수 $N$을 입력받는다. 순열 $P$는 참가자에게 주어지지 않는다.

구간 $[l,r]$의 LIS 길이를 질의하려면 다음 형식으로 출력한다.

? $l$ $r$

질의는 $1 \leq l \leq r \leq N$을 만족해야 한다. 인터랙터는 정수 를 출력한다.

• $1 \leq N \leq 100$.
• $P$는 $1,2,\cdots,N$의 순열이다.
• 질의 횟수는 최대 번이다.