葵さんは雪遊びをしている． 葵さんの目の前には N 個の雪玉が一直線上に並んでおり， 左から i 番目 (1 \leqq i \leqq N) の雪玉の大きさは A_i である．

葵さんは，最終的に大きな 1 つの雪玉を作りたいと考えている． そのために，以下の一連の操作を雪玉が 1 つになるか操作ができなくなるまで繰り返すことにした．

1. 隣接する 2 つの雪玉を選ぶ．このとき，左側の雪玉の大きさを l，右側の雪玉の大きさを r とすると，0 \leqq l-r \leqq 1 でなければならない．
2. 選んだ 2 つの雪玉を合成する．その結果，選んだ 2 つの雪玉は大きさ l+r の雪玉 1 つに置き換えられる．つまり，操作を行う前に左から大きさ s_1,s_2,\ldots,s_k の k 個の雪玉が並んでいるとき，左から t 番目 (1 \leqq t \leqq k-1) の雪玉と t+1 番目の雪玉を合成すると，操作後には左から大きさ s_1,s_2,\ldots,s_{t-1},s_t+s_{t+1},s_{t+2},\ldots,s_k の k-1 個の雪玉が並ぶ．

並んでいる雪玉の情報が与えられたとき，葵さんが適切に操作を行うことで雪玉を 1 つにすることができるか判定するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 500\,000．
• 1 \leqq A_i \leqq 10^{12} (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (15 点) A_1 = A_2 = \cdots = A_N．
2. (18 点) N \leqq 8．
3. (18 点) N \leqq 200．
4. (19 点) N \leqq 5\,000．
5. (30 点) 追加の制約はない．

入力例 1

5
1 1 1 1 1

出力例 1

Yes

例えば， 葵さんは次のように操作を行うことで最終的に雪玉を 1 つにすることができる．

1. 左から 4 番目と 5 番目の雪玉を選択し，合成する．操作後には左から大きさ 1,1,1,2 の雪玉が並ぶ．
2. 左から 1 番目と 2 番目の雪玉を選択し，合成する．操作後には左から大きさ 2,1,2 の雪玉が並ぶ．
3. 左から 1 番目と 2 番目の雪玉を選択し，合成する．操作後には左から大きさ 3,2 の雪玉が並ぶ．
4. 左から 1 番目と 2 番目の雪玉を選択し，合成する．操作後には左から大きさ 5 の雪玉が並ぶ．

この入力例はすべての小課題の制約を満たす．

入力例 2

3
2 2 2

出力例 2

No

葵さんがどのように操作を行っても雪玉を 1 つにすることはできない．

この入力例はすべての小課題の制約を満たす．

入力例 3

8
5 4 3 2 1 2 3 4

出力例 3

No

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 4

16
3 2 1 6 2 1 3 2 1 3 12 6 1 1 1 2

出力例 4

Yes

この入力例は小課題 3,4,5 の制約を満たす．