[比赛/考试专用OJ] 该 OJ 与 oj.socoding.cn 数据不互通,首次使用请注册账号。

1059. 兰道定理(15分)

Serein 举办了一场院运会,参赛项目有 1 题, 2 题, 4 题, 8 题, 15 题竞速编程等。比赛结束了,他迫切想要统计选手的得分情况。

设一共有 n 个选手参加了比赛。每次比赛都是两人对战,胜者加一分,败者不得分。现在将得分序列 s 按升序给出,也就是说序列的第 i(i > 1) 个元素 s_i 一定不小于它的上一个元素 s_{i-1}

院运会一共进行了 C_n^2 场比赛,即每两个人都对战过恰好一场。现在想要检验 s 序列是否是合法的。根据兰道定理,如果 s 能由两两对战得到,一定满足: \forall2\le k < n,\sum_{i=1}^ks_i\ge C_k^2\quad且\quad\sum_{i=1}^ns_i=C_n^2 其中 \sum_{i=1}^ns_is 序列的前 n 项和。即需要满足 s 的每个前 k 项和都不小于 C_k^2,且 s 的前 n 项和恰好为 C_n^2

给定 s,请你判断 s 是否是合法的。

输入

输入一行一个整数 n(2\le n\le10^3)

接下来输入一行 i 个整数,第 i 个整数为 s_i(0\le s_i\le 10^6),且 \forall 2\le i\le n,s_{i-1}\le s_i

输出

输出一行一个字符串,若 s 合法输出 yes,否则输出 no

样例

标准输入 复制文本
4
1 1 2 2
标准输出 复制文本
yes
标准输入 复制文本
4
0 0 0 6
标准输出 复制文本
no
标准输入 复制文本
4
1 1 1 2
标准输出 复制文本
no
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 177
通过 103