Permutation Subarray Query Counting

You are given a permutation \(\pi\) of numbers from \(1\) to \(n\), and \(q\) queries. Each query is represented by a quadruple \((l, r, x, y)\). For each query, you are to count the number of integer pairs \((u, v)\) that satisfy:

• \(l \le u \le v \le r\);
• For every \(i\) such that \(u \le i \le v\), the condition \(x \le \pi_i \le y\) holds.

In other words, for each query, you need to count the number of contiguous subarrays of the segment \([l, r]\) in which every element is between \(x\) and \(y\) (inclusive).

inputFormat

The first line of the input contains two integers \(n\) and \(q\), denoting the size of the permutation and the number of queries, respectively.

The second line contains \(n\) space-separated integers forming the permutation \(\pi\).

Each of the next \(q\) lines contains four integers \(l\), \(r\), \(x\), \(y\) representing a query.

outputFormat

For each query, output a single line containing the number of valid subarray (\(u, v\)) pairs that satisfy the given conditions.

sample

5 3
1 4 2 5 3
1 5 2 5
2 4 1 5
3 5 2 3

10
6
2