题目描述

给定一个长度为 $n$ 的数组 $a$。

你的任务是找到该数组所有子数组中平均值的最大可能值。

具体来说，给定任意下标 $l, r$，其中 $1 \leq l \leq r \leq n$，子数组 $a_l, a_{l+1}, \dots, a_r$ 的平均值定义为元素之和除以元素个数，即：

$$\texttt{avg}(l, r) = \frac{1}{r - l + 1} \sum_{i = l}^r a_i$$

请输出所有 $l, r$ 取值下，$\texttt{avg}(l, r)$ 的最大值。

注：数组 $b$ 是数组 $a$ 的子数组，如果 $b$ 可以通过删除 $a$ 的开头若干元素（可能为零或全部），以及末尾若干元素（也可能为零或全部），得到。在特定情况下，数组本身也是自己的子数组。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10$），即数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10$），表示数组中的元素。

输出格式

对于每个测试用例，输出一个整数，表示该数组所有子数组中平均值的最大值。

可以证明答案总是一个整数。

样例

3
4
3 3 3 3
5
7 1 6 9 9
5
3 4 4 4 3

3
9
4

样例说明

由 ChatGPT 5 翻译

来源

Codeforces 2162A，英文题名 Beautiful Average。