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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            solve(in);
        }
    }

    private static void solve(Scanner in) {
        int N = in.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        System.out.println(ans(A) ? "YES" : "NO");
    }

    private static boolean ans(int[] A) {
        long N = A.length;
        if (N == 1) {
            return true;
        }

        long sum = 0;
        for (long a : A) {
            sum += a;
        }

        final long round = (N * (N + 1)) / 2L;
        if (sum % round > 0) {
            return false;
        }

        final int K = (int) (sum / round);

        long k = K;

        for (int i = 0; i < N; i++) {
            int d = A[(int) ((i + 1) % N)] - A[i];
            if (d > K) {
                return false;
            }
            if (d < K) {
                int yobun = (K - d);
                if (yobun % N > 0) {
                    return false;
                }
                k -= yobun / N;
            }
            if (k < 0) {
                return false;
            }
        }

        return true;
    }
}