P3730 Manhattan Trading

Will opened an exchange in Manhattan. Every day, people come in a steady stream to buy and sell stocks. Now, Will wants to understand the stock holdings. Because there are simply too many people coming to trade, he needs you to write a program to help him with this task.

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

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

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

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