← 返回题目列表

Codeforces · 808/D

D. 数组除法

中文机器翻译题面 查看原题

Vasya 有一个由正整数组成的数组 a。 Vasya 想要将这个数组分成两个非空的连续部分(前缀和后缀),以便第一部分中所有元素的总和等于第二部分中元素的总和。这并不总是可能的,因此 Vasya 会在划分数组之前移动一些元素(Vasya 会删除一些元素并将其插入到任意位置)。

在删除元素的同一位置插入元素也被视为移动。

在选择要移动的正确元素及其新位置后,Vasya 可以划分数组吗?

输入

第一行包含单个整数 n (1 ≤ n ≤ 100000) — 数组的大小。

第二行包含 n 个整数 a1, a2... an (1 ≤ ai ≤ 109) — 数组的元素。

输出

如果 Vasya 可以在移动一个元素后分割数组,则打印 YES。否则打印NO。

示例

输入 #1

3
1 3 2

输出 #1

YES

输入 #2

5
1 2 3 4 5

输出 #2

NO

输入 #3

5
2 2 3 4 5

输出 #3

YES

注意

在第一个示例中,Vasya 可以将第二个元素移动到数组的末尾。

在第二个示例中,没有任何移动可以使除法成为可能。

在第三个示例中,Vasya 可以将第四个元素向左移动一个位置。