평균 최대화

양의 정수로 구성된 길이가 $m$ ($m ≥ 2$)인 수열 $x\[0], \cdots, x\[m - 1]$이 막힌 수열이라는 것은, 이 수열이 아래 조건을 만족한다는 것을 의미한다:

• $1$ 이상 $m - 2$ 이하의 모든 정수 $k$에 대해, $x\[k] > x\[0]$이고 $x\[k] > x\[m - 1]$이다.

즉, $x$의 양 끝 원소가 그 사이에 위치한 모든 원소보다 작다면 $x$는 막힌 수열이다.

예를 들어 $\[3, 7, 8, 4, 2]$과 $\[7, 7]$은 막힌 수열이지만, $\[5, 8, 4, 6, 7]$와 $\[3, 3, 4]$은 막힌 수열이 아니다. 정의에 의해 길이가 $2$인 모든 수열은 막힌 수열이고, 길이가 $1$ 이하인 수열은 막힌 수열일 수 없다는 점에 유의하라.

길이가 $K$인 수열 $X\[0], \cdots, X\[K - 1]$이 있을 때, 들어내기 연산은 $X\[i], \cdots, X\[j]$가 막힌 수열인 $(i, j)$을 골라, 수열에서 $X\[i + 1], \cdots, X\[j - 1]$을 제거하는 (즉, 수열을 $X\[0], \cdots, X\[i], X\[j], \cdots, X\[K - 1]$으로 바꾸는) 연산이다.

$f(X)$를 이러한 들어내기 연산을 원하는 대로 사용하여(사용하지 않을 수도 있고, 여러 번 사용할 수도 있음) 만들 수 있는 최종 수열의 평균의 최댓값이라고 정의하자.

예를 들어, $f(\[1, 3, 2, 100, 97, 98, 2, 3, 4, 1]) = 43$이며, 들어내기 연산을 아래와 같이 적용하면 된다.

• $i = 0$, $j = 2$를 선택하여 수열을 $\[1, 2, 100, 97, 98, 2, 3, 4, 1]$로 바꾼다.
• $i = 5$, $j = 8$을 선택하여 수열을 $\[1, 2, 100, 97, 98, 2, 1]$로 바꾼다.
• 최종 수열은 $\[1, 2, 100, 97, 98, 2, 1]$이며, 이 수열의 평균은 $(1 + 2 + 100 + 97 + 98 + 2 + 1)/7 = 43$이다.

양의 정수로 구성된 길이가 $N$인 수열 $A\[0], \cdots, A\[N -1]$이 주어진다. 여러분은 $A\[i], \cdots, A\[j]$가 막힌 수열이 되도록 하는 순서쌍 $(i, j)$가 주어질 때마다, $f(A\[i], \cdots , A\[j])$의 값을 구하는 프로그램을 작성해야 한다.

• $2 ≤ N ≤ 300\\, 000$
• $1 ≤ Q ≤ 600\\, 000$
• 모든 $i$에 대해 $1 ≤ A\[i] ≤ 10\\, 000\\, 000$ ($0 ≤ i ≤ N - 1$)
• 모든 maximum_average 호출에 대해 $0 ≤ i < j ≤ N - 1$이고, $A\[i], \cdots, A\[j]$가 막힌 수열이다.