Non-Decreasing Subarray Game
시간 제한2초메모리 제한256 MB
각 질의 구간에서 유토가 정수를 먼저 외쳐 점수를 최소화하고 플라티나가 그다음 정수를 외쳐 최대화할 때, 두 수가 정하는 구간 안의 비감소 부분 배열 개수를 구한다.
문제
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가 주어진다.
둘째 줄에는 배열의 값 A1, A2, A3, ..., AN이 주어진다.
셋째 줄부터 T+2번째 줄까지는 i번째 게임에서 설정한 수의 제한 L**i, R**i가 양의 정수로 주어진다. 이는 그 게임에서 두 사람이 부를 수 있는 수가 L**i 이상 R**i 이하라는 것을 뜻한다.
출력
각 게임별로 두 사람이 얻게 될 점수를 각 줄에 걸쳐 출력한다.
제한
- 1 ≤ N, T ≤ 500,000
- 1 ≤ A**i ≤ 109
- 1 ≤ L**i ≤ R**i ≤ N