该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个由 $n$ 个整数组成的数列 $a_1,a_2,\cdots,a_n$，请为这个数列找到一个平衡点，使得平衡点左侧与右侧的力矩尽量接近。

若平衡点为 $a_k$，则左侧力矩定义为数列中下标小于 $k$ 的各个元素到 $a_k$ 的距离乘以这些元素大小的总和。同理，右侧力矩定义为数列中下标大于 $k$ 的每个元素到 $a_k$ 的距离乘以这些元素大小的总和。

例如 $n=6$，若选 $a_4$ 为平衡，左力矩计算公式为：

右力矩计算公式为：

请找到一个最佳平衡点，并输出选择该点为平衡点时，左右力矩之差绝对值的最小值。

输入格式

第一行：单个整数表示 $n$； 第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

单个整数：表示在选择了最佳平衡点的前提下，两侧力矩之差绝对值的最小值。

4
1 2 3 4

0

样例解释 1

3号位为平衡点

数据范围

• $0\leq a_i\leq 1,000,000$；
• 对于 $30\%$ 的数据，$3 \leq n \leq 10,000$；
• 对于 $60\%$ 的数据，$3 \leq n \leq 50,000$；
• 对于 $100\%$ 的数据，$3 \leq n \leq 300,000$。