Count Intervals with Mex in Range

Given a sequence bot of length \( n \). There are \( q \) queries. For each query, you are given three integers \( l, x, y \). Your task is to determine the number of intervals \( [l, r] \) (with \( l \le r \)) such that the \( \text{mex} \) of the subarray \( \{ bot_l, bot_{l+1}, \ldots, bot_r \} \) lies in the range \( [x, y] \).

The \( \text{mex} \) (minimum excluded) of a multiset \( S \) is defined as the smallest non-negative integer that does not appear in \( S \). For example, \( \text{mex}(\{0, 1, 1, 3\}) = 2 \).

inputFormat

The input consists of multiple lines:

• The first line contains two integers \( n \) and \( q \): the length of the sequence and the number of queries.
• The second line contains \( n \) integers: \( bot_1, bot_2, \ldots, bot_n \).
• Each of the next \( q \) lines contains three integers \( l, x, y \) describing a query.

outputFormat

For each query, output a single integer on a new line: the number of intervals starting at \( l \) whose \( \text{mex} \) value lies in the range \( [x, y] \).

sample

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

2
3
5