Description

在游戏中的王国里，有n个城市，第i个城市有a[i]个士兵。现在为了加强国防，需要定一个城市为“首都”，当“首都”出现突发情况时，各城市的士兵都会赶来首都。对于第i和j个城市，它们的距离为|i-j|。现在，小明需要定首都，在突发情况时，使得每一个士兵赶到首都的路程之和最小。你能再帮帮小明吗？

Input Format

两行，第一行为一个正整数n，表示城市的总数；第二行为n个整数，代表每个城市的士兵数。

Output Format

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

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

Hint

【样例说明】

样例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。

【数据范围】

对于80%的数据，1≤n≤1000，1≤a[i]≤100；

对于100%的数据，1≤n≤1000000，1≤a[i]≤1000。