SP21834 SACITY - Sadde and His City

Sadde 是一个国家的国王，这个国家名叫 Sadde 土地。在 Sadde 土地的每个城市里，建筑物都排成一行。 为了了解各个城市的得分，Sadde 请他的大臣 Dukker 来负责这项任务。 在每个城市中，有 $N$ 栋建筑物排成一行，每个建筑物前面都有一个容器。对于每个建筑物，Dukker 计算出该建筑物左边比它矮的建筑物数量（记作 **Hmin $_{i}$**），以及右边比它高的建筑物数量（记作 **Hmax $_{i}$**）。接着，他在第 $i$ 栋建筑物的容器中放入 **Hmin $_{i}$ + Hmax $_{i}$** 个旗帜。 Dukker 将所有建筑物的容器收集起来并随机打乱。现在，他希望能将这些旗帜平均分配到所有建筑物，使得每个建筑物得到的旗帜数量相同，而每个建筑物只能从一个容器中获取旗帜。 城市的得分就是每个建筑物能够获得的最大旗帜数量。

输入包含 $T$ 组测试数据。每组测试数据有两行。第一行为一个整数 $N$，表示城市中的建筑物数量。第二行包含 $N$ 个整数，代表每个建筑物的高度 $H_i$。

输出包含 $T$ 行，每行代表一个城市的得分。

- $1 \leq T \leq 1000$ - $1 \leq N \leq 1000$ - $1 \leq H_i \leq 1000000$ **本翻译由 AI 自动生成**