Counting Inversion Subarrays

You are given two integers \( c \) and \( d \) and an array \( a_1, a_2, \ldots, a_n \). There are \( q \) queries, each consisting of an interval \( [l, r] \). For each query, consider all non-empty subarrays \( a_x, a_{x+1}, \ldots, a_y \) with \( l \le x \le y \le r \). Let the inversion count of a subarray be defined as

[ inv(a_x,\ldots,a_y)=\sum_{i=x}^{y} \sum_{j=i+1}^{y} \left[ a_i>a_j \right], ]

where \( [P] \) is an Iverson bracket which is \( 1 \) if the predicate \( P \) is true and \( 0 \) otherwise. For each query, count the number of subarrays whose inversion count is between \( c \) and \( d \) (inclusive), i.e.,

[ \sum_{x=l}^{r},\sum_{y=x}^{r} \left[ c \le inv(a_x,\ldots,a_y) \le d \right]. ]

</p>

Note:

• The notation \( [l,r] \) denotes an interval.
• The notation \( [p] \) with a proposition \( p \) is the Iverson bracket.

inputFormat

The first line contains four integers \( n \), \( q \), \( c \), and \( d \) where \( n \) is the length of the array and \( q \) is the number of queries.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \), representing the array.

Each of the next \( q \) lines contains two integers \( l \) and \( r \), representing a query interval.

outputFormat

For each query, output a single integer on a new line, representing the number of subarrays within \( [l, r] \) whose inversion count is between \( c \) and \( d \) (inclusive).

sample

3 2 0 0
1 2 3
1 2
1 3

3
6

</p>