#P0847. 小B数数

小B数数

题目描述

给定一个长度为 nn 的数组 aa 。

你的任务是找出该数组中任意子数组的最大平均值。

具体来说,对于任意满足 1≤l≤r≤n 1 \leq l \leq r \leq n 的下标l,r l, r ,定义子数组 al,al+1,…,ara_l, a_{l+1}, \ldots, a_r 的平均值为元素之和除以元素个数,即:

要求输出所有可能的(l,r)(l,r)中 avg(l,r)avg(l,r) 中的最大值。

注意:∗数组 bb 是数组 aa 的子数组,当且仅当 bb 可以通过从 aa 的开头和结尾各删去若干(可能是零个或全部)元素得到。特别地,数组本身也是它自己的子数组。

输入格式

第一行包含一个整数 t(1≤t≤10) t ( 1 \leq t \leq 10)——测试用例的数量。

对于每个测试用例:

  1. 第一行包含一个整数 n(1≤n≤10)n ( 1 \leq n \leq 10 )——数组 a 的长度。
  2. 第二行包含 n n 个整数 a1,a2,…,an(1≤ai≤10) a_1, a_2, \ldots, 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