题目描述

在游戏中的王国里，有 $n$ 个城市，第 $i$ 个城市有 $a_i$ 个士兵。现在为了加强国防，需要定一个城市为“首都”，当“首都”出现突发情况时，各城市的士兵都会赶来首都。对于第 $i$ 和 $j$ 个城市，它们的距离为 $|i-j|$ 。

现在，小明需要定首都，在突发情况时，使得每一个士兵赶到首都的路程之和最小。你能再帮帮小明吗？

输入格式

第一行为一个正整数 $n$ ，表示城市的总数；

第二行为 $n$ 个整数，代表每个城市的士兵数。

数据范围

对于 80% 的数据， $1 \le n \le 1000$ ，$1 \le a_i \le 100$ ；

对于 100% 的数据， $1 \le n \le 1000000$ ， $1 \le a_i \le 1000$ 。

输出格式

输出两个整数，为每一个士兵赶到首都的路程之和的最小值,以及所选作为首都的城市的编号。

样例

5
10 20 30 40 50

150 4

3
10 1 1

3 1

10
9 1 1 3 2 5 3 7 5 4

108 6

样例解释

样例 1 : 把 4 号城市定为首都，答案为:

a[1]×|1-4|+a[2]×|2-4|+a[3]×|3-4|+a[4]×|4-4|+a[5]×|5-4|=10×3+20×2+30×1+50×1=150，可以证明此为最小值。

样例 2 : 把 1 号城市作为首都，答案为 1×1+1×2=3。