[模拟]Codeforces Circle of Students

There are

Students want to start a round dance. A clockwise round dance can be started if the student

For example, if the indices of students listed in clockwise order are

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle.

You have to answer

Input

The first line of the input contains one integer

The first line of the query contains one integer

The second line of the query contains a permutation of indices

Output

For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

Example

input

Copy

output

Copy

YES
YES
NO
YES
YES

模拟题，长度只有200，看能不能完整绕一圈就好了，中间要两两之差绝对值为1且保持单调性，可以允许一次单调性的改变

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e3+5;
 4 int a[amn];
 5 int main(){
 6     int q,n;
 7     cin>>q;
 8     while(q--){
 9         cin>>n;
10         for(int i=1;i<=n;i++)cin>>a[i];
11         int valid=1;
12         if(n>1){
13             int ed=n,f=a[2]-a[1],fr=1;
14             for(int i=1;i!=ed;){
15                 int nex=i+1<=n?i+1:1;
16                 if(abs(a[i]-a[nex])!=1){
17                     if(fr){ed=i,fr=0;f=(i==1)?-f:f;i=(i+1<=n)?i+1:1;continue;}
18                     else {valid=0;break;}
19                 }
20                 if(i==ed)break;
21                 if(f>0){
22                     if(abs(a[i]-a[nex])!=1||a[nex]-a[i]<0){valid=0;break;}
23                 }
24                 else if(f<0){
25                     if(abs(a[i]-a[nex])!=1||a[nex]-a[i]>0){valid=0;break;}
26                 }
27                 else {valid=0;break;}
28                 i=(i+1<=n)?i+1:1;
29             }
30         }
31         if(valid)cout<<"YES\n";
32         else cout<<"NO\n";
33     }
34 }
35 /***
36 模拟题，长度只有200，看能不能完整绕一圈就好了，中间要两两之差绝对值为1且保持单调性，可以允许一次单调性的改变
37 51234
38 15432
39 ***/