Description

• $N$ people line up in a row. For simplicity, each person holds exactly one stock.
• Different people may hold the same stock.
• Define the popularity of a stock as the number of people who hold that stock.
• Each time, Will will ask a query: among the people in a contiguous interval, what is the popularity of the stock with the $k$-th smallest popularity?

Input Format

• The first line contains two positive integers $N,M$, representing the number of people and the number of queries.
• The next line contains $N$ positive integers, where $a_i$ is the stock held by the $i$-th person.
• The next $M$ lines each contain three positive integers $l,r,k$, representing a query asking for the $k$-th smallest popularity in the interval $[l, r]$. It is guaranteed that $l\leq r$.

Output Format

• For each query, output one integer on a separate line, which is the $k$-th smallest popularity value in the interval $[l, r]$.
• If $k$ is greater than the number of distinct stocks in the interval, output $-1$.

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

1  
3  
2  
-1

Hint

For $20\%$ of the testdata, $N,M\leq 1000$.

For another $10\%$ of the testdata, all queries have $l=1, r=N$.

For $100\%$ of the testdata, $1\leq N, M\leq 10^5$，$1\leq a_i\leq 10^9$.

Translated by ChatGPT 5