Yuto와 Platina가 Non-Decreasing Subarray Game을 하려고 한다. 게임은 길이 N의 배열 A에서 진행된다.

Yuto가 먼저 정수 하나를 부르고, 그걸 듣고 Platina가 정수를 하나 부른다. 이때 얻게 되는 점수는 둘이 부른 수 중 크지 않은 수를 a, 작지 않은 수를 b라고 했을 때, a ≤ i ≤ j ≤ b이며 구간 [i, j]가 Non-Decreasing Subarray를 이루는 서로 다른 (i, j) 쌍의 개수이다.

이때 [i, j]가 Non-Decreasing Subarray 를 이룬다는 것은 주어진 배열에서 i ≤ x ≤ y ≤ j이면, A_x ≤ A_y라는 것을 뜻한다.

Yuto는 점수가 최소화되기를 원하며, Platina는 점수가 최대화되기를 원한다. 이 게임은 너무나도 재미있어서 부를 수 있는 수의 제한을 바꿔가면서 게임을 T판 진행하려고 한다! 각 판마다 둘이 얻게 될 점수를 구하여라.

입력 형식

첫째 줄에는 두 양의 정수 N과 T가 주어진다.

둘째 줄에는 배열의 값 A₁, A₂, A₃, ..., A_N이 주어진다.

셋째 줄부터 T+2번째 줄까지는 i번째 게임에서 설정한 수의 제한 L_i, R_i가 양의 정수로 주어진다. 이는 그 게임에서 두 사람이 부를 수 있는 수가 L_i 이상 R_i 이하라는 것을 뜻한다.

출력 형식

각 게임별로 두 사람이 얻게 될 점수를 각 줄에 걸쳐 출력한다.

예제 입력

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

예제 출력

4
1
4
7
3