평균 최대화

양의 정수로 이루어진 길이가 $m$ ($m \ge 2$)인 수열 $x[0], \cdots, x[m - 1]$이 막힌 수열이라는 것은, $1$ 이상 $m - 2$ 이하의 모든 정수 $k$에 대해 $x[k] > x[0]$이고 $x[k] > x[m - 1]$이라는 뜻이다. 즉, 양 끝 원소가 그 사이의 모든 원소보다 작으면 막힌 수열이다. 예를 들어 $[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$이다. $(0, 2)$를 골라 $[1, 2, 100, 97, 98, 2, 3, 4, 1]$을 얻고, 다시 $(5, 8)$을 골라 $[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 \le N \le 300\,000$
• $1 \le Q \le 600\,000$
• 모든 $i$에 대해 $1 \le A[i] \le 10\,000\,000$ ($0 \le i \le N - 1$)
• 모든 maximum_average 호출에 대해 $0 \le i < j \le N - 1$이고, $A[i], \cdots, A[j]$가 막힌 수열이다.