Yuto와 Platina는 비내림차순 부분 배열 게임(Non-Decreasing Subarray Game)을 하려고 합니다. 이 게임은 길이가 $N$인 배열 $A$에서 진행됩니다.

Yuto가 먼저 정수를 하나 말하고, 그 다음에 Platina가 정수를 하나 말합니다. 플레이어들이 선택하는 숫자는 $L$부터 $R$ 사이의 구간에 포함되어야 합니다. 두 플레이어가 선택한 정수를 $a$와 $b$라고 하고, $a \le b$가 되도록 순서를 정합니다. 이때 게임의 점수는 $a \le i \le j \le b$를 만족하는 모든 쌍 $(i, j)$ 중에서 구간 $[i, j]$가 배열 $A$의 비내림차순 부분 배열을 이루는 것들의 개수입니다.

구간 $[i, j]$가 비내림차순 부분 배열이라는 것은, $i \le x \le y \le j$를 만족하는 모든 $x$와 $y$에 대해 $A[x] \le A[y]$가 성립함을 의미합니다.

Yuto는 점수를 최소화하려고 하고, Platina는 점수를 최대화하려고 합니다. 이 게임은 매우 재미있어서 $T$번 진행할 예정입니다. 모든 게임은 동일한 배열 $A$를 사용하지만, 각 게임마다 $L$과 $R$의 값은 다를 수 있습니다.

두 플레이어 모두 최적으로 게임을 진행한다고 가정할 때, 각 게임에서 얻게 될 점수를 구하세요.

입력

첫 번째 줄에는 배열의 길이 $N$과 게임의 횟수 $T$ ($1 \le N, T \le 500\,000$)가 주어집니다.

두 번째 줄에는 배열의 값 $A[1], A[2], A[3], \dots, A[N]$이 주어집니다 ($1 \le A[i] \le 10^9$).

다음 $T$개의 줄에는 각 게임의 $L_i$와 $R_i$ ($1 \le L_i \le R_i \le N$)가 주어집니다.

출력

각 게임마다 해당 게임의 점수를 별도의 줄에 출력하세요.

예제

입력 1

8 5
7 10 3 1 9 5 5 2
1 5
2 2
5 8
1 8
3 5

출력 1

4
1
4
7
3