There are N boxes arranged in a circle. The i-th box contains A_i stones.

Determine whether it is possible to remove all the stones from the boxes by repeatedly performing the following operation:

* Select one box. Let the box be the i-th box. Then, for each j from 1 through N, remove exactly j stones from the (i+j)-th box. Here, the (N+k)-th box is identified with the k-th box.



Note that the operation cannot be performed if there is a box that does not contain enough number of stones to be removed.

Constraints

* 1 ≦ N ≦ 10^5
* 1 ≦ A_i ≦ 10^9

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N


Output

If it is possible to remove all the stones from the boxes, print `YES`. Otherwise, print `NO`.

Examples

Input

5
4 5 1 2 3


Output

YES


Input

5
6 9 12 10 8


Output

YES


Input

4
1 2 3 1


Output

NO
from operator import sub

N = int(input())
data = list(map(int, input().split()))
step = N * (N+1) // 2
total = sum(data)
#print("-->", total, step)
if total % step:
  print("NO")
else:
  K = total // step
  #print("-->", total, step, K)
  datar = [data[i % N] for i in range(-1, N)] 
  delta = list(map(sub, datar[1:], datar))
  #print(*delta)
  #print("-->", *list(map(lambda x:(K-x) % N, delta)))
  #print("-->", *list(map(lambda x:(K-x) // N, delta)))
  if any(map(lambda x:(K-x) % N, delta)):
    print("NO")
  elif any(map(lambda x: K-x < 0, delta)): 
    print("NO")
  else:    
    ops = list(map(lambda x:(K-x) // N, delta))
    if sum(ops) == K:
      for i, v in enumerate(data[0:1]):
        vv = sum([ops[(i-k) % N] * (k+1) for k in range(N)])
        if v != vv:        
          print("NO")
          break
      else:    
        print("YES")
    else:
      print("NO")
    