P10814 [Template] Offline 2D Point Counting

Frogs.

You are given a sequence $a$ of length $n$. There are $m$ queries. Each query gives $l, r, x$. Find the number of elements in the interval $[l, r]$ that are less than or equal to $x$.

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence $a$. The following $m$ lines each contain three integers $l, r, x$, representing one query.

For each query, output one line with one integer, the answer.

For $20\%$ of the testdata, $1 \le n, m, a_i, l, r, x \le 100$. For $40\%$ of the testdata, $1 \le n, m, a_i, l, r, x \le 10^4$. For $60\%$ of the testdata, $1 \le n, m, a_i, l, r, x \le 10^5$. For $80\%$ of the testdata, $1 \le n, m, a_i, l, r, x \le 10^6$. For $100\%$ of the testdata, $1 \le n, m, a_i, l, r, x \le 2 \times 10^6$. Translated by ChatGPT 5