길이 M인 양의 정수열 X_1, \dots, X_M이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자.

수열 X_1, \dots, X_M이 오름차순이라는 것은, 각 i (1 \le i \le M-1)에 대해 X_i \le X_{i+1}이라는 것이다.

수열 X를 오름차순으로 만들기 위해, 수열 X에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

연산을 최소 횟수로 적용해서 X를 오름차순으로 만들 때, 이 최소 횟수를 f(X)라고 하자.

길이 N의 양의 정수열 A_1, \dots, A_N과 쿼리 Q개가 주어진다.

각 쿼리에는 1 \le l \le r \le N을 만족하는 정수 l과 r이 주어진다. 해당 쿼리에 대한 답은 f(A_l, \dots, A_r)이다.

A_l, \dots, A_r은 A의 l번째 원소부터 r번째 원소까지로 이루어진 부분 수열을 의미한다.

각 쿼리에 대한 답을 구하여라.

[제약 조건]

오름차순 timer 4초 memory 1024MB

오름차순 4초 1024MB