Description

街道上很多酒店，交易葡萄酒，正数为卖出葡萄酒，负数为需要葡萄酒，总需求量和总售出量是相等的，从一家店到另外一家店需要路费（路费=距离×运酒量），假设每家店线性排列且相邻两店之间距离都是1,求最小路费。

Format

Input

有两行整数，第一行整数代表有n个居民，第二行代表每个居民的需求，整数代表买进，负数代表卖出；n<=100000

Output

一个整数，最小路费。

Samples

5
5 -4 1 -3 1

9

6
-1000 -1000 -1000 1000 1000 1000

9000

Limitation

1s, 1024KiB for each test case.