{"code":"trungvique","name":"MEDIAN QUERY","description":"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)$.\r\n\r\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).\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa số nguyên dương $n$ không quá $10^5$.\r\n- Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,...,a_n$ $(a_i \\le 10^5)$\r\n- 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.\r\n- $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)$\r\n\r\n

Output

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6\r\n 7 9 1 7 8 2\r\n 3\r\n 1 3\r\n 3 6\r\n 1 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 7\r\n 2\r\n 7\r\n ```","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}