Subarray Count with Bounded Maximum and Minimum

Given a sequence \(a_1, a_2, \dots, a_n\) of length \(n\) (with each \(a_i\) in the range \([1,4000]\)), you are to answer \(m\) queries. Each query provides four positive integers \(L_1, R_1, L_2, R_2\) (satisfying \(1 \le L_1 \le R_1 \le 4000\) and \(1 \le L_2 \le R_2 \le 4000\)). For each query, count the number of subarrays \([l,r]\) (with \(1 \le l \le r \le n\)) such that the maximum value in \(a_l,a_{l+1},\dots,a_r\) lies in \([L_1, R_1]\) and the minimum value lies in \([L_2, R_2]\).

Note: Since the number of queries \(m\) can be very large, it is recommended to precompute the answers for all possible pairs of maximum and minimum values and then answer each query in \(O(1)\) time using a 2D prefix sum.

The formulas used are as follows. Let \(f(x,y)\) be the number of subarrays whose maximum is \(x\) and minimum is \(y\). We then build a 2D prefix sum array: \[ P(x,y) = \sum_{i=1}^{x} \sum_{j=1}^{y} f(i,j), \] so that for a query \((L_1,R_1,L_2,R_2)\) the answer is computed as: \[ P(R_1, R_2) - P(L_1-1, R_2) - P(R_1, L_2-1) + P(L_1-1, L_2-1). \]

inputFormat

The first line contains two integers \(n\) and \(m\): the length of the sequence and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (each in the range \([1,4000]\)).

Each of the next \(m\) lines contains four integers \(L_1\), \(R_1\), \(L_2\), \(R_2\) describing a query.

outputFormat

Output \(m\) lines. The \(i\)th line contains a single integer representing the answer to the \(i\)th query.

sample

3 2
1 2 3
1 3 1 2
2 3 1 1

5
2