밥의 평균

밥은 원소 개수가 홀수인 배열의 평균을 구하는 새로운 방법을 생각해 냈다. 배열의 길이가 1보다 큰 동안 다음 연산을 반복한다. 왼쪽 끝을 $l$, 오른쪽 끝을 $r = l + 2$로 하는 길이 3의 구간을 임의로 고르고, 세 원소의 중앙값을 구한 뒤 세 원소를 중앙값 하나로 바꾼다. 세 원소의 중앙값은 그중 두 번째로 큰 원소이다. 예를 들어 $[1, 5, 4]$의 중앙값은 $4$이고, $[2, 2, 2]$의 중앙값은 $2$이다.

배열 $[4, 1, 3, 2, 5]$에서 $l = 2$, $r = 4$를 고르면 $[1, 3, 2]$의 중앙값은 $2$이므로 배열은 $[4, 2, 5]$가 된다. 이어서 $l = 1$, $r = 3$을 고르면 $[4, 2, 5]$의 중앙값은 $4$이므로 배열은 $[4]$가 된다.

결과는 구간을 어떻게 고르느냐에 따라 달라진다. 밥은 마지막에 남는 수가 가능한 한 가장 커지도록 구간을 고른다. 이렇게 얻은 수를 밥의 평균이라고 부른다.

원소가 $n$개인 배열 $a$에 대해 $q$개의 질의에 답해야 한다. $j$번째 질의는 $L_j$, $R_j$로 주어지며, 부분 배열 $[a_{L_j}, a_{L_j+1}, \ldots, a_{R_j}]$의 밥의 평균을 구한다. 모든 질의의 구간 길이는 홀수이다.

첫째 줄에 배열의 크기 $n$ ($3 \leq n \leq 5 \cdot 10^4$)이 주어진다.

둘째 줄에 배열의 원소 $a_i$ ($0 \leq a_i \leq 10^9$) $n$개가 주어진다.

셋째 줄에 질의의 개수 $q$ ($1 \leq q \leq 10^5$)가 주어진다.

이어지는 $q$개의 줄에 두 정수 $L_j$, $R_j$ ($1 \leq L_j \leq R_j \leq n$)가 주어진다. $R_j - L_j + 1$은 홀수이다.

$j$번째 줄에 $j$번째 질의의 답을 정수 하나로 출력한다.