Thứ Hạng Trong Đoạn · canuc80k5902

Cho mảng tĩnh $a_{1}, a_{2}, \dots, a_{n}$ . Với mỗi truy vấn gồm ba số $l, r, k$ , hãy xét đa tập các phần tử $a_{l}, a_{l + 1}, \dots, a_{r}$ và tìm phần tử nhỏ thứ $k$ . Các phần tử có cùng giá trị vẫn được tính theo số lần xuất hiện.

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ , lần lượt là độ dài mảng và số truy vấn.
Dòng thứ hai chứa $n$ số nguyên của mảng.
Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $l, r, k$ .

Output

Với mỗi truy vấn, in phần tử nhỏ thứ $k$ trong đoạn $[l, r]$ trên một dòng.

Constraints

$1 \leq n, m \leq 2 \cdot 1 0^{5}$ .
$0 \leq a_{i} \leq 1 0^{9}$ .
$1 \leq l \leq r \leq n$ .
$1 \leq k \leq r - l + 1$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n, m \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

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

Output

Giải thích: Đoạn đầu sau khi sắp xếp là $0, 0, 2, 4, 4, 5, 7$ , nên phần tử nhỏ thứ ba là $2$ . Trong đoạn $[3, 6]$ , thứ tự tăng là $0, 2, 4, 7$ , do đó phần tử nhỏ thứ tư bằng $7$ .

Ý tưởng: Nén các giá trị khác nhau thành các hạng từ 1 đến s. Với mỗi tiền tố a_1..a_i, xây một gốc cây tần suất root[i]; gốc mới được tạo từ root[i-1] bằng cách tăng một đơn vị tại hạng của a_i.
Ý tưởng: Trong truy vấn [l,r], số phần tử thuộc bất kỳ miền giá trị nào bằng hiệu số đếm giữa root[r] và root[l-1]. Khi đi từ gốc xuống, tính số phần tử trong nửa trái. Nếu số đó ít nhất k, đáp án ở nửa trái; nếu không, bỏ qua toàn bộ nửa trái và tìm thứ k-leftCount ở nửa phải.
Ý tưởng: Đúng đắn. Hiệu hai cây tiền tố chứa đúng tần suất của đoạn. Quyết định ở mỗi mức giữ lại chính xác miền chứa phần tử thứ k; đến lá, hạng thu được là hạng của đáp án. Giải nén hạng trả đúng giá trị gốc.
Ý tưởng: Độ phức tạp. Tiền xử lý O(n log n), mỗi truy vấn O(log n), bộ nhớ O(n log n).