L-最大平均数_2025年广州大学程序设计竞赛新生赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

给定长度为 $n$ 的整数数组 $a=(a_1,\dots,a_n)$ ，且每个数均为 $6$ 的倍数。对于 $1\le i<j\le n$ ，定义 $f(i,j) = \max_{\, i \leq l < r \leq j} \frac{a_l + a_{l+1} + \cdots + a_r}{r - l + 1}$

即 $f(i,j)$ 表示区间 $[i,j]$ 内所有长度至少为 $2$ 的连续子区间的平均值的最大值。

请计算 $\sum_{1\le i<j\le n} f(i,j).$

可以证明上述和为整数。

输入描述:

第一行包含一个整数 $n\ (2 \le n \le 5 \times 10^3)$ 。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n, \ ( 1 \le a_i\le 10^9 )$ 且每个 $a_i$ 是 $6$ 的倍数。

输出描述:

输出一个整数，表示 $\sum_{1\le i<j\le n} f(i,j)$ 的值。

示例1

输入

复制

2
6 12

输出

复制

示例2

输入

复制

5
6 12 18 12 6

输出

复制