Background

Frogs.

Problem Description

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$.

Input Format

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.

Output Format

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

6 4
1 1 4 5 1 4
1 6 3
1 6 4
1 1 4
1 5 4

3
5
1
4

Hint

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