평균 최대화

양의 정수로 구성된 길이가 $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])$의 값을 구하는 프로그램을 작성해야 한다.

평균 최대화

문제

제한