시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 107 33 24 26.374%

문제

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

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

이때 [i, j]가 Non-Decreasing Subarray 를 이룬다는 것은 주어진 배열에서 ixyj이면, Ax Ay라는 것을 뜻한다.

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

입력

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

둘째 줄에는 배열의 값 A1, A2, A3, ..., AN이 주어진다.

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

출력

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

제한

  • 1 ≤ NT ≤ 500,000
  • 1 ≤ Ai ≤ 109
  • 1 ≤ Li Ri ≤ 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