MEDIAN QUERY

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy số nguyên dương \(a_1,a_2,...,a_n\) gồm \(n\) phần tử. Bạn sẽ phải trả lời \(q\) truy vấn, mỗi truy vấn trả lời số trung vị của đoạn \([A_L;A_R]\) \((1 \le L \le R \le n)\).

Định nghĩa: Số trung vị của 1 dãy số là số nằm ở vị trí thứ \(\frac{n}{2} + 1\) sau khi sắp xếp dãy đó tăng dần (với \(n\) lẻ) hoặc ở vị trí thứ \(\frac{n}{2}\) (nếu \(n\) chẵn).

Input

Dòng đầu chứa số nguyên dương \(n\) không quá \(10^5\).
Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^5)\)
Dòng thứ ba chứa số nguyên dương \(q\) không quá \(1000\) - số truy vấn cần trả lời.
\(q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(L, R\) \((1 \le L \le R \le n)\)

Output

Ứng với mỗi truy vấn, in ra kết quả thỏa mãn đề bài.

Example

Test 1

Input

6
7 9 1 7 8 2
3
1 3
3 6
1 1

Output

7
2
7

Bình luận

6

dang7rickroll 5:23 p.m. 22 Tháng 2, 2022

Gửi tới admin: Em không biết là ai đã đổi nhưng nếu có thay đổi gì thì nhờ các thầy/cô/anh/chị ghi chú vào giúp em để em biết ạ, em cảm ơn. (Cụ thể là ai đó đã đổi dạng bài từ a_luyen tap (thầy Đông) sang Bài toán truy vấn (Query))

2

Toilaaibanbietko7A4 9:28 a.m. 23 Tháng 2, 2022

Giờ lại thành Cày trâu / Duyệt (Brute-force) ròi :))))

2

huyhau6a2 5:47 p.m. 22 Tháng 2, 2022

Chắc là có ngưòi khác làm admin ở ẩn mà mình không biết rồi hmm

7 bình luận nữa