Non-Decreasing Subarray Game

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 ≤ Ay라는 것을 뜻한다.

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

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

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

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

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

• 1 ≤ N, T ≤ 500,000
• 1 ≤ A**i ≤ 109
• 1 ≤ L**i ≤ Ri ≤ N