Background

Problem Description

You are given a sequence $bot$ of length $n$.

There are $q$ queries. Each query gives three numbers $l, x, y$. For each query, find how many intervals $[l, r]$ (with $l \le r$) starting at $l$ satisfy $\text{mex}(\{bot_l, bot_{l+1}, \cdots, bot_r\}) \in [x, y]$.

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

Input Format

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries.

The second line contains $n$ numbers, representing the sequence $bot$.

The next $q$ lines each contain three integers $l, x, y$.

Output Format

Output $q$ lines in total. Each line contains one integer, representing the answer.

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

2
0

10 10
0 0 1 1 1 0 0 1 0 1
1 0 0
2 0 1
3 1 2
4 0 1
5 0 2
6 0 1
7 1 1
8 2 2
9 0 0
10 1 2

0
1
5
2
6
2
1
2
0
0

Hint

For $100\%$ of the data, $1 \le n, q \le 3 \times 10^5$, $0 \le bot_i < n$, $0 \le x \le y \le n$, $1 \le l \le n$.

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n, q \le 300$.
• Subtask 2 (15 pts): $n, q \le 2000$.
• Subtask 3 (15 pts): $bot_i \le 1$.
• Subtask 4 (20 pts): $x = y$.
• Subtask 5 (40 pts): No special constraints.

Translated by ChatGPT 5