一个装置的初始电量为 0，将按顺序执行 n 次电量调整。第 i 次调整使电量增加 a_i；a_i 可以为负数。装置没有电量上限，但在每次调整后，电量都不能为负。

开始执行前，你可以选取至多一个非空连续区间，将这个区间内的调整顺序反转。每次调整的数值不变，区间外的顺序不变。

判断能否让装置完成全部调整。不需要输出反转区间。

输入格式

本题只有一组输入数据。

第一行包含整数 n。第二行包含 n 个整数 a_1,a_2,…,a_n。

输出格式

如果存在满足要求的方案，输出 YES；否则输出 NO。

数据范围

• 1 ≤ n ≤ 200000；
• −10^9 ≤ a_i ≤ 10^9。

样例 1

6
2 -3 6 -6 4 -3

YES

说明：反转第 2 至 5 次调整，顺序变为 2,4,−6,6,−3,−3，每次调整后的电量分别为 2,6,0,6,3,0。

样例 2

6
2 -3 7 -7 4 -3

NO

下载样例数据