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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

/*07:05:45PM

String x =sc.next();
char inp [] = x.toCharArray();
	SimpleDateFormat displayFormat = new SimpleDateFormat("HH:mm");
	SimpleDateFormat parseFormat = new SimpleDateFormat("hh:mm a");
	Date date = parseFormat.parse(x.substring(0, 5)+" "+x.substring(8, 10));
	System.out.println(displayFormat.format(date)+":"+x.substring(6, 8));
 */

public class Main
{
	public static int V , E ,dfsNumberCounter , dfs_low[] , dfs_num[]  , visited [] , numCC;
	public static ArrayList<Integer> adjList [];
	public static Stack<Integer> S;
	public static void tarjanSCC(int u )
	{
		dfs_low[u] = dfs_num[u]= dfsNumberCounter++;
		S.push(u);
		visited[u]=1;
		for(int j =0 ; j < adjList[u].size() ; j++)
		{
			int v = adjList[u].get(j);
			if(dfs_num[v]==-1)
				tarjanSCC(v);
			if(visited[v]==1)
				dfs_low [u]=Math.min(dfs_low[u], dfs_low[v]);
		}
		
		if(dfs_low[u]==dfs_num[u])
		{
			numCC++;
			while(true)
			{
				int v =S.pop();
				visited[v]=0;
				if(u==v)break;
			}
		}
		}
		
	public static boolean check(int arr[])
	{
		for(int i =0 ; i< arr.length ; i++)
			if(arr[i]!=i)return false;
		return true;
	}
	public static void change(int arr[])
	{
		for(int i =0 ; i<arr.length ;i++)
			if(i%2==0)
				if(arr[i]+1==arr.length)arr[i]=0;
				else arr[i]++;
			else if(arr[i]-1==-1)arr[i]=arr.length-1;
					else  arr[i]--;
	}
	public static void main(String[] args) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt(); 
		int arr [] = new int[n];
		for(int i =0 ; i < n ; i++)arr[i]=sc.nextInt();
		boolean ok =false;
		for(int i =0 ; i< 1001 && ! ok; i++)
		{
			if(!check(arr))
				change(arr);
			else ok=true;
		}
		if(ok)System.out.println("YES");
		else System.out.println("NO");
	}
	
	
}












class Pair
{
	public int  x  ; int y;
	Pair(int a , int b )
	{
		x=a;y=b;
	}
	@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		return x==((Pair)(obj)).x && y==((Pair)obj).y;
	}

	
	
	
}




class Scanner
{
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s)
	{
		br = new BufferedReader(new InputStreamReader(s));
	}

	public String next() throws IOException
	{
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

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

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

	public String nextLine() throws IOException
	{
		return br.readLine();
	}

	public double nextDouble() throws IOException
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if (x.charAt(0) == '-') {
			neg = true;
			start++;
		}
		for (int i = start; i < x.length(); i++)
			if (x.charAt(i) == '.') {
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			} else {
				sb.append(x.charAt(i));
				if (dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg ? -1 : 1);
	}

	public boolean ready() throws IOException
	{
		return br.ready();
	}

}
