$1, 2, ..., N$의 순열 $P = (P_1, P_2, ..., P_N)$이 주어진다.
정수열 $x = (x_1, x_2, ..., x_k)$에 대해, x의 점수를 x의 i번째 원소가 x의 i+1번째 원소보다 작은 인덱스 i의 개수로 정의한다.
다음 쿼리를 Q번 처리한다.
양의 정수 l, r이 주어진다. 1 이상 l 이하 r 이하 N을 만족한다. $X = (P_l, P_l+1, ..., P_r)$에 대해 다음 문제를 푼다.
X의 비어 있지 않은 부분수열이 가질 수 있는 점수의 최댓값을 M이라고 하자. 점수가 M인 비어 있지 않은 부분수열 중 길이의 최솟값을 구한다.
부분수열이란, 어떤 수열에서 0개 이상의 원소를 제거하고 남은 원소들의 순서를 그대로 유지해서 얻을 수 있는 수열이다.
입력은 표준 입력에서 다음 형식으로 주어진다.