26613번 - 수열과 구간과 구간과 구간과 쿼리

길이가 $N$인 정수 수열 $A_1, A_2, ..., A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• $a, b, c, d$: $a\leq x\leq b, c\leq y\leq d$를 만족하는 두 정수 $x, y$에 대해 부분 수열 $A_x, A_{x+1}, ..., A_y$의 평균의 최댓값을 출력한다.

첫째 줄에 수열의 길이 $N(1 \leq N \leq 100,000)$과 쿼리의 개수 $Q(1\leq Q \leq 30,000)$가 주어진다.

둘째 줄에는 $A_1, A_2, ..., A_N$이 주어진다.$(1 \leq A_i \leq 10^8)$

셋째 줄부터 $Q$개의 줄에는 쿼리 $a, b, c, d$가 한 줄에 하나씩 주어진다.$(1\leq a\leq b\leq c\leq d\leq N)$

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

답은 버림하여 정수로 출력한다.