A - Equalizing Water Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、 N 個のタンクが横一列に並んだ水道システムを管理しています。各タンクには 1 から N までの番号が左から順についており、タンク i には現在 A_i リットルの水が入っています。

高橋君は、このシステムの水量を調整するために、以下の操作を何回でも（ 0 回でもよい）行うことができます。操作ごとに選ぶタンクの組は自由に変えられます。

操作: 隣り合う 2 つのタンク i と i + 1 （ 1 \leq i \leq N - 1 ）を選び、一方のタンクから他方のタンクへ水を 1 リットル移す。すなわち、次のいずれかを行う。

  • タンク i の水を 1 リットル減らし、タンク i + 1 の水を 1 リットル増やす。
  • タンク i + 1 の水を 1 リットル減らし、タンク i の水を 1 リットル増やす。

ただし、各タンクの水量はどの操作の実行後においても 0 以上でなければなりません。すなわち、水が 0 リットルのタンクから水を減らす操作は行えません。

この操作では水の総量は変化しないことに注意してください。

高橋君は、操作を繰り返すことで、すべてのタンクの水量を等しくしたいと考えています。これが達成可能かどうかを判定してください。可能な場合は Yes を、不可能な場合は No を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9
  • 入力はすべて整数である

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、タンクの個数を表す整数 N が与えられる。
  • 2 行目には、各タンクに入っている水の量を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

すべてのタンクの水量を等しくすることが可能な場合は Yes を、不可能な場合は No を 1 行で出力せよ。

入力例 1

3
1 2 3

出力例 1

Yes

入力例 2

4
1 2 3 5

出力例 2

No

入力例 3

6
0 1000000000 500000000 200000000 100000000 200000000

出力例 3

No

Score : 200 pts

Problem Statement

Takahashi manages a water system consisting of N tanks arranged in a horizontal row. The tanks are numbered from 1 to N from left to right, and tank i currently contains A_i liters of water.

To adjust the water levels in this system, Takahashi can perform the following operation any number of times (including zero times). The pair of tanks chosen can be different for each operation.

Operation: Choose two adjacent tanks i and i + 1 (1 \leq i \leq N - 1), and transfer 1 liter of water from one tank to the other. Specifically, perform one of the following:

  • Decrease the water in tank i by 1 liter and increase the water in tank i + 1 by 1 liter.
  • Decrease the water in tank i + 1 by 1 liter and increase the water in tank i by 1 liter.

However, the water level in each tank must remain 0 or more after every operation. That is, you cannot decrease the water in a tank that has 0 liters of water.

Note that this operation does not change the total amount of water.

Takahashi wants to make the water levels of all tanks equal by repeating operations. Determine whether this is achievable. If it is possible, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9
  • All input values are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of tanks.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the amount of water in each tank.

Output

If it is possible to make the water levels of all tanks equal, output Yes; otherwise, output No, in a single line.

Sample Input 1

3
1 2 3

Sample Output 1

Yes

Sample Input 2

4
1 2 3 5

Sample Output 2

No

Sample Input 3

6
0 1000000000 500000000 200000000 100000000 200000000

Sample Output 3

No