Cho mảng \(A\) gồm \(N\) phần tử. Bạn cần thực hiện \(Q\) truy vấn: với mỗi truy vấn, tìm số trung vị (median) của đoạn con từ vị trí \(L\) đến \(R\) (1-indexed).

Ở đây, số trung vị của một đoạn con độ dài \(len\) được định nghĩa là phần tử đứng ở vị trí thứ \(\lfloor \frac{len + 1}{2} \rfloor\) (1-indexed) sau khi các phần tử trong đoạn được sắp xếp tăng dần.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số trung vị trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

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

Output:

4
2
4

Giải thích:

• Truy vấn 1: Đoạn \([1..3]\) là \([4, 2, 7]\), độ dài 3. Vị trí trung vị là \(\lfloor \frac{3+1}{2} \rfloor = 2\) (phần tử nhỏ thứ 2), sắp xếp là \([2, 4, 7] \to\) chọn 4.
• Truy vấn 2: Đoạn \([2..5]\) là \([2, 7, 1, 5]\), độ dài 4. Vị trí trung vị là \(\lfloor \frac{4+1}{2} \rfloor = 2\), sắp xếp là \([1, 2, 5, 7] \to\) chọn 2.
• Truy vấn 3: Toàn mảng độ dài 5. Vị trí trung vị là 3, sắp xếp \([1, 2, 4, 5, 7] \to\) chọn 4.