题目描述

有一栋 $M$ 层的大楼。每层的住户数量分别为 $K_1, K_2, K_3, \ldots, K_m$。有一天，所有住户一起回家，并且他们乘坐同一部电梯（假设电梯足够大）。由于某些原因，电梯只能在某一层停靠，住户们必须上楼或者下楼才能到达自己的家。每一位住户向上走 $N$ 层，其不满意程度会增加 $N \times a + 0.5 \times N \times (N - 1)$ 度；每一位住户向下走 $N$ 层，其不满意程度会增加 $N \times b + 0.5 \times N \times (N - 1)$ 度。你的任务是判断电梯应该停在哪一层，以便使总的不满意程度尽可能低。

输入

输入的第一行包含一个整数 $T$（$1 \leq T \leq 20$），表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $M$（$1 \leq M \leq 10000$）、$a$ 和 $b$（$0 \leq a, b \leq 100$）。第二行包含 $K_1, K_2, K_3, \ldots, K_m$（$0 \leq K_i \leq 20$，$i = 1..M$）。

输出

对于每个测试用例，输出一行，包含一个整数，表示电梯应该停靠的楼层。

输入数据 1

1
5 3 2
1 1 1 1 1

输出数据 1

3

来源

POJ 月赛 -- 2004.07.18