Tý có một bệnh viện theo dõi chỉ số sức khỏe của \(N\) bệnh nhân theo thứ tự khám bệnh. Mỗi bệnh nhân có một chỉ số a_i là số nguyên dương. Bác sĩ muốn thực hiện Q truy vấn: với đoạn bệnh nhân từ L đến R, hãy tìm chỉ số trung vị (phần tử đứng ở vị trí chính giữa sau khi sắp xếp tăng dần). Nếu độ dài đoạn là chẵn, lấy phần tử ở vị trí \(\lfloor (len+1)/2 \rfloor\).

Hãy viết chương trình giúp bác sĩ tìm trung vị nhanh chóng.

Đị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 thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, mỗi dòng là chỉ số trung vị của đoạn tương ứng.

Ví dụ

Input:

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

Output:

3
4
4

Giải thích:

• \([1,5]\) sắp xếp: \(\{1,2,3,5,8\}\) — trung vị là \(3\). - [2,6]$ sắp xếp: \(\{1,2,3,6,8\}\) — trung vị là 3. (Sao chép ví dụ sai, tính lại: \(\{3, 2, 8, 1, 6\}\) sắp xếp \(\{1, 2, 3, 6, 8\}\) → \(3\)). - [3,7]$ sắp xếp: \(\{2,4,6,8,1\}\) sai. Đúng: \(\{2,8,1,6,4\}\) sắp xếp \(\{1,2,4,6,8\}\) → \(4\).

Subtask