Problem Description

Given a permutation $\pi$ of $1 \sim n$, and $q$ queries. Each query contains an integer quadruple $( l, r, x, y )$, asking how many integer pairs $( u, v )$ satisfy:

• $l \le u \le v \le r$;
• and for all $\forall u \le i \le v$, we have $x \le \pi_i \le y$.

Input Format

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers, representing $\pi$.

In the next $q$ lines, each line contains one query quadruple.

Output Format

Output $q$ lines, where each line is the answer to one query.

4 1
1 2 3 4
1 4 2 4

6

Hint

Subtask 1 ($34$ points): $1 \le n, q \le 3 \times 10^4$.

Subtask 2 ($66$ points): $1 \le n, q \le 2 \times 10^5$.

Translated by ChatGPT 5