15337 | 지루함

문제 설명

Ilya는 Metropolis 공항의 대기 구역에 앉아 자신의 비행기가 지연된다는 내용을 계속해서 보여 주는 시간표를 보는 데 싫증이 났다. 그래서 종이 한 장을 꺼내 몇 가지 문제를 풀기로 했다.

먼저 Ilya는 크기가 n × n인 격자를 그리고 그 위에 n개의 칸을 표시했는데, 표시된 어떤 두 칸도 같은 행이나 같은 열에 속하지 않는다. 그는 변이 격자의 변과 평행한 격자 위의 직사각형에서 꼭짓점 칸 중 정확히 두 개가 표시되어 있으면 그 직사각형을 아름답다고 부른다. 아름다운 직사각형은 정확히 n·(n - 1) / 2개 있다.

Ilya는 변이 격자의 변과 평행한 q개의 질의 직사각형을 격자 위에서 선택했으며(반드시 아름다운 직사각형일 필요는 없다), 각 직사각형의 아름다움 정도를 구하고 싶어 한다. 직사각형의 아름다움 정도는 주어진 직사각형과 적어도 한 칸을 공유하는 아름다운 직사각형의 수이다.

이제 Ilya는 비행기가 출발할 때까지 문제를 풀 시간이 충분하지 않을 수도 있다고 생각한다. 표시된 칸과 질의 직사각형에 대한 설명이 주어질 때, Ilya가 각 질의 직사각형의 아름다움 정도를 구하도록 도와준다.

입력 형식

입력의 첫 번째 줄에는 격자의 크기와 질의 직사각형의 수를 나타내는 두 정수 n와 q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000)이 주어진다.

두 번째 줄에는 공백으로 구분된 n개의 정수 p1, p2, ..., pn (1 ≤ pi ≤ n, all pi are different)이 주어지며, 이들은 Ilya가 표시한 격자 칸을 지정한다. 열 i에서 그는 pi번째 행의 칸을 표시했다. 행은 아래에서 위로 1부터 n까지 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨진다.

이어지는 q개의 줄은 질의 직사각형을 설명한다. 각 직사각형은 네 정수 l, d, r, u (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ u ≤ n)로 설명되며, 여기서 l과 r은 각각 직사각형의 가장 왼쪽 열과 가장 오른쪽 열이고, d과 u는 각각 가장 아래쪽 행과 가장 위쪽 행이다.