n 개의 수와 이 수열의 시작지점과 끝 지점이 주어질 때 해당 구간을 정렬 후 중앙값을 찾는게 문제이다.

입력

• 첫 줄에는 수열의 크기 n ( 1 <= n <= 100,000) 이 주어지고
• 다음 줄에는 수열이 .. 수열의 시작위치는 1 이다. 각 수는 -100 이상 100 이하이다.
• 다음 줄에는 질의 수 q ( 1 <= q <= 100,000) 가 주어지고
• 다음 q 개의 줄에는 시작 구간과 끝 구간이 주어진다.

출력

** n개의 수일 때, [n/2]번째 위치의 수를 출력한다. ( [a] = a보다 작거나 같은 최대 정수 )

입출력 예

입력

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

출력

6
2
7

입출력 보충

오름차순 기준 2번째 수를 출력하면 됩니다.

출처:Fate