Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Background

The spherical elf pl launched Slay before taking the ABC contest. At this moment, the coach came in, so he had to pretend to be working on data structures.

Problem Description

Given a sequence $a$ of length $n$, you need to support $m$ operations of the following type: let $x$ be the $k$-th smallest value in $a_l, a_{l + 1}, \ldots, a_r$, afind the number of elements equal to $x$ in $a_l, a_{l + 1}, \ldots, a_r$.

Input Format

The first line contains two positive integers $n, m\ (1 \le n, m \le 2 \times 10^5)$, representing the length of the sequence and the number of subsequent operations respectively.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n\ (1 \le a_i \le 10^9)$, describing the sequence.

Each of the next $m$ lines contains three positive integers $l, r, k\ (1 \le l \le r \le n, 1 \le k \le r - l + 1)$.

Output Format

For each query, output a single line with a positive integer representing the answer to that query.

Samples

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

1
1
2