Số nhỏ thứ k (K-th Number)

Nguồn: POJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một dãy gồm $n$ số nguyên đôi một khác nhau. Mỗi truy vấn $Q(i,j,k)$ yêu cầu tìm phần tử nhỏ thứ $k$ nếu sắp xếp đoạn $a_i..a_j$ theo thứ tự tăng dần.

Dữ liệu vào

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau. Mỗi trong $m$ dòng tiếp theo chứa $i,j,k$.

Kết quả

Với mỗi truy vấn, in giá trị nhỏ thứ $k$ của đoạn.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 1000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n\le10^5$
• $1\le m\le5000$
• $|a_i|\le10^9$ và các $a_i$ đôi một khác nhau
• $1\le i\le j\le n$
• $1\le k\le j-i+1$

Ví dụ

Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output

5
6
3

Giải thích

Đoạn $[2,5]$ là [5,2,6,3]. Sau khi sắp xếp ta có [2,3,5,6], nên số nhỏ thứ ba là $5$.