Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of gears.

The second line contains n digits a1, a2, ..., an (0 ≤ ai ≤ n - 1) — the sequence of active teeth: the active tooth of the i-th gear contains number ai.

Output

In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.

Examples

Input

3
1 0 0


Output

Yes


Input

5
4 2 1 4 3


Output

Yes


Input

4
0 2 3 1


Output

No

Note

In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.
import java.io.*;
import java.util.*;
public class Main {
	public static int MOD;
	static int[][] arr;
	static int n;
	public static void main(String[] args) throws Exception
	{
		MyScanner input = new MyScanner();
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = input.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++)
			arr[i] = input.nextInt();
		
		for (int i =0; i <=n; i++)
		{
			if(!t(arr))
			{
				arr = doIt(arr);
				//print(arr);
			}
			else
			{
				System.out.println("YES"); return;
			}
		}
		System.out.println("NO");
		
		
	

	}

	private static void print(int[] arr2) {
		// TODO Auto-generated method stub
		for(int i : arr2)
			System.out.print(i + " ");
		System.out.println();
		
	}

	public static int[]  doIt(int[] arr)
	{
		int n = arr.length;
		for(int i = 0;i < n; i++)
		{
			if( i % 2 == 0)
			{
				arr[i] = (arr[i] + 1 +n) % n;
			}
			else
			{
				arr[i] = (arr[i] - 1 +n) % n;
			}
		}
		return arr;
	}
	public static boolean t(int[] arr)
	{
		boolean b = true;
		for(int i = 0; i < arr.length; i++)
		{
			if(arr[i] != i)
				b = false;
		}
		return b;
	}
	private static class MyScanner 
	{
		BufferedReader br;
		StringTokenizer st;

		public MyScanner(String s) 
		{

			try
			{
				br = new BufferedReader(new FileReader(s));
			} catch (IOException e)
			{
				e.printStackTrace();
			}

		}

		public MyScanner() 
		{
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		public String next() 
		{
			if (st == null || !st.hasMoreElements()) 
			{
				try 
				{
					String line = br.readLine();
					if (line == null) {
						throw new UnknownError();
					}
					while (line.trim().equals("")) {
						line = br.readLine();
						if (line == null) {
							throw new UnknownError();
						}
					}
					st = new StringTokenizer(line);
				} 
				catch (IOException e) 
				{
					throw new UnknownError();
				}
			}
			return st.nextToken();
		}

		public String nextLine() {
			try {
				String line = br.readLine();
				if (line == null) {
					throw new UnknownError();
				}
				return line;
			}
			catch (IOException e) {
				throw new UnknownError();
			}
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}
}