There are n students standing in a circle in some order. The index of the i-th student…
- User
There are n students standing in a circle in some order. The index of the i-th student is p_i. It is guaranteed that all indices of students are distinct integers from 1 to n (i. e. they form a permutation).
Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student n comes right after the student n - 1 in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student i should be right after the student i - 1 in counterclockwise order (this condition should be met for every i from 2 to n).
For example, if the indices of students listed in clockwise order are [2, 3, 4, 5, 1], then they can start a clockwise round dance. If the students have indices [3, 2, 1, 4] in clockwise order, then they can start a counterclockwise round dance.
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 q independent queries. Input
The first line of the input contains one integer q (1 ≤ q ≤ 200) — the number of queries. Then q queries follow.
The first line of the query contains one integer n (1 ≤ n ≤ 200) — the number of students.
The second line of the query contains a permutation of indices p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is the index of the i-th student (in clockwise order). It is guaranteed that all p_i are distinct integers from 1 to n (i. e. they form a permutation).
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
5 4 1 2 3 4 3 1 3 2 5 1 2 3 5 4 1 1 5 3 2 1 5 4
Output
YES YES NO YES YES
Assistant
We need to interpret problem: There are n students standing in a circle in some order. The index of the i-th student is p_i. This is the permutation given in input, representing the clockwise order of the students? The problem statement: "There are n students standing in a circle in some order. The index of the i-th student is p_i." That might be ambiguous: likely it means the students are arranged around the circle in clockwise order: student 1 (the first in the list) has index p_1, student 2 (the second in the list) has index p_2, ..., student n (the nth) has index p_n. And they are arranged in that order around the circle. So the sequence p is the clockwise order of indices around the circle. But careful: The problem states: "The first line of the query contains one integer n — the number of students. The second line of the query contains a permutation of indices p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is the index of the i-th student (in clockwise order)." So indeed p_i is the index of the student that occupies the i-th position in clockwise order. So the circle order (starting from some arbitrary point and going clockwise) is given by the list p.
Now, we need to determine if they can start a round dance. A clockwise round dance can be started if the student 2 comes right after student 1 in clockwise order (no students between them), student 3 comes right after student 2, etc., and student n comes right after student n-1. Essentially, the indices must appear in consecutive increasing order around the circle (1,2,3,...,n) in the clockwise direction. But note: The circle is cyclic, so after n comes 1? Actually the condition says: student n comes right after student n-1 in clockwise order. It doesn't mention student 1 after n? In a clockwise round dance, it seems that the sequence must be exactly 1,2,3,...,n in clockwise order, and then the circle completes, but after n the next student would be back to the start? Actually if there are exactly n students, and they form a circle, the condition "student 2 comes right after student 1 in clockwise order, student 3 right after student 2, ..., student n right after student n-1" ensures that the sequence of indices in clockwise order is exactly [1,2,...,n] (in that order) if we consider the order starting from student 1. But note: It does not require that student 1 comes right after student n. Because after student n, the circle goes back to the first student, but that could be any. Actually if the order is exactly [1,2,...,n] in clockwise order, then after n, the next (clockwise) is the first student in the circle, which would be 1 again? But in a circle of n distinct students, the order is cyclic: the student after the last is the first. So if the clockwise order is exactly the list [1,2,3,...,n] (starting from some point), then indeed after n, the next student is 1 (since the first student is the one at the start of the list). But the condition doesn't explicitly mention that; but it's automatically satisfied because the circle is closed. However, the condition that "student 2 comes right after student 1", "student 3 after student 2", ..., "student n after student n-1" does not say anything about the relationship between student n and student 1. So it's possible that the sequence is [1,2,3,...,n] but also there could be a gap between n and 1? Actually in a circle, after the last student in clockwise order (the n-th position if we list from some starting point), the next student is the first student in the list (since the list wraps around). So if we list the circle order starting from some arbitrary point, we have p_1, p_2, ..., p_n in clockwise order. The condition for clockwise round dance is: there exists some rotation of the sequence (or maybe exactly the given sequence from the specified starting point? The problem says "Your task is to determine whether it is possible to start a round dance." The students cannot change positions. That means with the given circle (starting point unspecified? Actually the input gives a specific ordering: p_1 is the index of the i-th student in clockwise order. So the starting point is fixed: the first element in the list is some student. But in a circle, the starting point is arbitrary. However, since the circle is given as a list starting from some point, that point is defined. But we can choose any starting point to start the dance? The dance doesn't require a designated start; it's just whether the arrangement is such that all students are in consecutive order (either increasing or decreasing) around the circle. Usually for such problems (like Codeforces Round Dance problem), it's checking if the given permutation (circular arrangement) is such that it's a "cyclic shift" of [1,2,...,n] or its reverse. I recall a known Codeforces problem: "Round Dance" maybe problem 1450A? Actually I think this is Codeforces problem #1611A? Not sure. But let's analyze.
Better to re-read the problem statement precisely:
"There are n students standing in a circle in some order. The index of the i-th student is p_i. It is guaranteed that all indices of students are distinct integers from 1 to n (i. e. they form a permutation).
Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student n comes right after the student n - 1 in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student i should be right after the student i - 1 in counterclockwise order (this condition should be met for every i from 2 to n)."
Given the arrangement, we need to decide if it is possible to start a round dance (either clockwise or counterclockwise). So we need to check if either condition holds.
Interpretation: In the given circle, for clockwise round dance: If we look at the circle in clockwise direction, we should see indices in increasing order 1,2,3,...,n consecutively. But the circle might start at any point: that is, the sequence around the circle (starting from any student and going clockwise) must be exactly a cyclic shift of [1,2,...,n] (i.e., the circle is just the numbers in order). But wait: The condition only requires that for each i from 2 to n, student i is immediately after student i-1 in clockwise order. It doesn't require that student 1 is immediately after student n. So does it allow the arrangement where the circle order is [1,2,...,n] but there could be other students in between n and 1? No, because there are exactly n students, and the condition "student i is immediately after student i-1" for all i means that all n students are arranged in a chain such that 1->2->3->...->n are consecutive. But since there are exactly n students, that chain uses up all students. So after n, the next student clockwise must be something. But it could be student 1? But then student 1 would be immediately after student n, which is not required but would happen if the chain uses all students and the circle closes. However, what if the chain does not use all students? That's impossible because there are n distinct indices from 1 to n, so the chain from 1 to n includes all n indices. So the chain includes all students. So after student n, the next student clockwise would be the student that is after n in the circle order. Since there are no other students left (all are already placed), the only student left to be after n is student 1? But is student 1 already placed? Yes, student 1 is somewhere. For the chain 1->2->...->n to be consecutive, student 2 must be immediately after 1, 3 after 2, ..., n after n-1. That means the positions of these n students are in a contiguous block in the circle? But in a circle, there is no end, so "contiguous block" wrapped around maybe. However, if we have a chain of n distinct elements in a circle, they must occupy all positions. The condition says that for each i from 2 to n, the immediate clockwise neighbor of student i-1 is student i. That means if we start from student 1 and go clockwise, we encounter student 2, then student 3, ..., then student n. After student n, the next clockwise neighbor is some student; but it's not constrained. But since all students are already accounted for (the set is all numbers 1..n), the only possible neighbor after n would be some student that hasn't been visited yet in the chain, but there is none because we've visited all n students in the chain? Actually if we start at student 1 and go clockwise, we would visit student 2, then 3,..., then n. After that, if we continue clockwise, we would come back to the starting point, which is student 1 (since circle). But is it required that the neighbor after n is student 1? In a circle, each student has exactly two neighbors. If we have visited all students in a sequence that goes 1,2,...,n, then after n, the next student must be the student that is clockwise after n. Since there are exactly n students, the only student not yet visited in that direction? But we visited all students in the sequence, but the sequence is not necessarily a cycle: In a linear order, if we list them as they appear around the circle, we will eventually loop back. But if we have a circle and we list them in clockwise order starting from some point, we get a cyclic sequence. If we start listing from student 1 and go clockwise, we would get a sequence that eventually returns to student 1 after n steps. So if the condition holds that 2 is after 1, 3 after 2, ..., n after n-1, then when we go clockwise from 1 we encounter 2,3,...,n. After n, if we continue, we must encounter the student who is clockwise of n, which by the circle must be the student that was before 1 originally. But is that student necessarily 1? Actually the student before 1 (in clockwise order) is the student that when going clockwise, you get to 1 after that student. But if we start at 1 and go clockwise, after n we get to some student. But since we have listed n students total, after n steps we would have visited all n students if the sequence 1..n includes all students, but wait: The sequence from 1 to n includes n distinct numbers. Starting from 1, after visiting 2,3,...,n, we have visited n students. That is all the students. So the next student after n must be the one we started at, which is 1. Because the circle contains exactly those n students, and the order is cyclic. So indeed, after n, the next must be 1. Therefore, the condition automatically implies that student 1 is immediately after student n in clockwise order. But is that explicitly required? The condition only states for i=2..n, but due to the cyclic nature and the fact that all n students are used, it forces that. But let's check: Could there be a scenario where the chain 1->2->...->n uses all students but the circle order is such that after n, we go to some student that is not 1? But if we have all n students, and we have a chain of immediate successors: succ(1)=2, succ(2)=3, ..., succ(n-1)=n. Then the function succ is defined for all except possibly n. The circle defines a permutation on the set of students: each student has exactly one clockwise neighbor (a successor) and one counterclockwise neighbor (predecessor). Since we have assigned succ(1)=2, succ(2)=3, ..., succ(n-1)=n, we have not yet defined succ(n). However, because each student must have exactly one successor, and each student must be successor of exactly one other (since it's a cycle), we must have succ(n) = some student x. But x must be a student that doesn't already have a predecessor? Actually, in a directed cycle, each node has in-degree 1 and out-degree 1. We've assigned outgoing edges for 1..n-1. The node n's outgoing edge not assigned. For the cycle to be a single cycle containing all nodes, succ(n) must be the one node that hasn't got an incoming edge yet, which is? Let's see incoming edges: succ(1)=2 => predecessor of 2 is 1; succ(2)=3 => pred(3)=2; ... succ(n-1)=n => pred(n)=n-1. So nodes 2..n have predecessors assigned. Node 1 does not have a predecessor assigned yet (since no succ(x)=1). So succ(n) must be 1 to complete the cycle. So indeed it is forced. So the condition for clockwise round dance is exactly that the permutation p (when considered as a circular arrangement) is a cyclic shift of [1,2,...,n] (i.e., the order of indices around the circle is exactly the consecutive numbers in increasing order, starting from some point). Similarly, counterclockwise round dance would require that the order in counterclockwise direction (or equivalently, the order in clockwise direction is a decreasing order: n, n-1, ..., 1) but because it's counterclockwise, the condition is: student i is immediately after student i-1 in counterclockwise order for i=2..n. That translates to: when moving counterclockwise from student 1, we see student 2, then 3, ..., then n. That is equivalent to moving clockwise we see the reverse order: from student 1, clockwise neighbor should be n? Actually let's think.
Define clockwise order as given by list p: p_1 -> p_2 -> ... -> p_n -> back to p_1 is clockwise. Then counterclockwise order is the reverse direction: from p_i, going counterclockwise leads to p_{i-1} (with p_0 = p_n). So the condition for counterclockwise round dance: For i=2..n, student i is right after student i-1 in counterclockwise order. That means if you stand at student i-1 and go counterclockwise, the immediate student you encounter is student i. In terms of clockwise order, that means student i is the immediate clockwise predecessor? Let's convert: Let succ_cw(x) denote clockwise neighbor of student x. Then the counterclockwise neighbor (ccw) is the student whose clockwise neighbor is x? Actually in a circle, if we have clockwise order, then the counterclockwise neighbor of x is the student that has x as its clockwise neighbor. So if ccw(x) = y, then succ_cw(y) = x. The condition: for i from 2 to n, ccw(i-1) = i, i.e., the counterclockwise neighbor of student i-1 is student i. Equivalently, succ_cw(i) = i-1? Because if ccw(i-1)=i, then going counterclockwise from i-1 you get i, meaning that i is the student that comes before i-1 when moving clockwise? Actually careful: In a circle, we have ordering. Suppose we label positions in clockwise order: ... -> A -> B -> C -> ... Then clockwise neighbor of A is B; clockwise neighbor of B is C; etc. Counterclockwise neighbor of B is A; counterclockwise neighbor of C is B. So ccw(B)=A. So the relationship: ccw(X) = Y means that succ_cw(Y) = X. Because if Y is the counterclockwise neighbor of X, then going clockwise from Y you reach X. So indeed ccw(X) = Y ⇔ succ_cw(Y) = X.
Thus condition ccw(i-1) = i translates to succ_cw(i) = i-1. So for each i from 2 to n, the clockwise successor of student i is student i-1. That means succ_cw(2)=1, succ_cw(3)=2, ..., succ_cw(n)=n-1. Also succ_cw(1) would be forced to be n? Let's see: We have succ_cw(2)=1, succ_cw(3)=2,..., succ_cw(n)=n-1. Now, what about succ_cw(1)? It must be the student whose counterclockwise neighbor is 1? But from the cycle condition, we can deduce that the only student left without a predecessor? Let's check incoming: succ_cw(2)=1 so pred_cw(1)=2? Actually pred_cw is the clockwise predecessor; but easier: Since each student has exactly one clockwise successor, we assigned succ_cw for 2..n. For node 1, its successor is not assigned yet. For node ? Also, we need to check if any node has two incoming: For succ_cw(i)=i-1, the predecessor (the node that points to i-1) is i. So for each i from 2 to n, node i points to i-1. So nodes i-1 for i=2..n get incoming from i. That means nodes 1..n-1 have an incoming edge (from i = that node+1). Node n? Node n gets incoming from? succ_cw(?) = n? Not yet assigned. Also node 1's incoming? pred_cw(1) is from succ_cw(?) =1. According to our assignments, we have succ_cw(2)=1 so node 1 gets incoming from 2. So node 1 already has an incoming edge from 2. Node 2 gets incoming from 3, etc. Node n-1 gets incoming from n. Node n has no incoming edge yet. So to complete a single cycle, succ_cw(1) must be n (since node n needs an incoming edge, and node 1 needs an outgoing edge). So indeed succ_cw(1)=n. Therefore the clockwise order becomes: starting from 1, its clockwise neighbor is n; then from n, succ is n-1? Wait succ_cw(n)=n-1, so from n go to n-1; then from n-1 go to n-2; ... eventually from 2 go to 1. So the clockwise order (starting from 1) would be: 1, n, n-1, ..., 2, and then back to 1. That is a decreasing sequence from n down to 2 after 1. More generally, if the circle order is any rotation of that, it would work. So the counterclockwise round dance condition is equivalent to the clockwise order being a cyclic shift of [1, n, n-1, ..., 2] i.e., decreasing order except starting at 1 then decreasing. But careful: The condition we derived says succ_cw(i) = i-1 for i=2..n, and succ_cw(1)=n. That is exactly the cycle (1 -> n -> n-1 -> ... -> 2 -> 1). So the clockwise order around the circle is this cycle: starting from 1, clockwise: 1, n, n-1, ..., 2. That is a decreasing order (if we list after 1, we see n, n-1,...,2). But if we start from some other point, the order might be a rotation of that sequence. For example, the example given: [3,2,1,4] in clockwise order can start a counterclockwise round dance. Let's test: The list is [3,2,1,4]. Is that a rotation of the sequence [1,4,3,2]? Actually for n=4, the cycle from condition is 1 -> 4 -> 3 -> 2 -> 1. So clockwise order could be [1,4,3,2] or its rotations: [4,3,2,1], [3,2,1,4], [2,1,4,3]. Indeed [3,2,1,4] is a rotation: starting at 3, we have 3,2,1,4. That fits. So yes.
Thus the problem reduces to: Given a permutation p representing the clockwise order around the circle (starting from some arbitrary point), determine if p is a cyclic rotation of either the identity permutation [1,2,...,n] or the permutation that is [1, n, n-1, ..., 2] (i.e., 1 followed by decreasing sequence from n to 2). Actually careful: For clockwise round dance, the clockwise order must be a rotation of [1,2,...,n]. For counterclockwise, the clockwise order must be a rotation of [1, n, n-1, ..., 2]. That is one possible representation. But also note: Could the counterclockwise condition also be satisfied if the clockwise order is a rotation of [n, n-1, ..., 1]? Let's check: If clockwise order is [n, n-1, ..., 1], then starting from n, clockwise: n, n-1,...,1. For a counterclockwise round dance, we need that going counterclockwise from 1 gives 2, from 2 gives 3,...? Actually we derived condition succ_cw(i)=i-1 for i>=2 and succ_cw(1)=n. That yields clockwise order from 1: 1, n, n-1,...,2. So the clockwise order is not decreasing from n to 1, but 1 then decreasing from n to 2. However, if we rotate, we could get e.g., [n, n-1,...,2,1]? Let's check: Starting from n, the cycle would be n, n-1,...,2,1. Is that a rotation of 1,n,n-1,...,2? The cycle is the same cycle, just starting point different. The cycle is: 1 -> n -> n-1 -> ... -> 2 -> 1. So if we list starting from n, we get: n, n-1,...,2,1. That is indeed a rotation of the base sequence (starting at n). So the clockwise order could be any rotation of that cycle. So the set of valid sequences for counterclockwise round dance is exactly the set of sequences that when read clockwise, are cyclic rotations of the cycle (1, n, n-1, ..., 2). So one can check by testing if p (or any rotation) matches either pattern.
Since n ≤ 200, we can simply brute force: For each query, we can check if the sequence p is a rotation of the increasing sequence [1..n] OR a rotation of the sequence [1, n, n-1, ..., 2]. But note that the input p is a permutation, and it's given as the clockwise order starting from some student (the first element). The circle doesn't have a designated starting point, but the input fixes one. However, the condition for round dance is about the arrangement, not about the specific starting point of the list. In other words, we can rotate the circle arbitrarily; the starting point of the list is just an arbitrary reference. The problem statement: "The second line of the query contains a permutation of indices p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is the index of the i-th student (in clockwise order)." That means the order as given is the clockwise order starting from some specific student (the one they call the first). So the circle's orientation and starting point are fixed by the input. But the round dance can be started from any student? Actually, the condition for round dance does not require a specific starting point; it just says that if the arrangement satisfies the consecutive condition (for all i, i is immediately after i-1 in clockwise order), then they can start a round dance. However, that condition is a property of the entire circle, not depending on where we start counting. So we need to check if the circle (as an unlabeled cycle) is exactly the cycle (1-2-...-n) in clockwise direction, or the cycle (1-n-...-2) in clockwise direction. Since the input gives a specific linear representation starting from some arbitrary point, we need to check if that cycle (as a cyclic permutation) equals either of those cycles.
Thus we can take p as a circular list. Check if either p is a cyclic rotation of inc = [1,2,...,n] or a cyclic rotation of dec = [1, n, n-1, ..., 2]. That's straightforward: we can generate all rotations of p (n possibilities) and compare to inc and dec. Or we can locate the position of 1 in p, then check if from that position going clockwise we see increasing order (2,3,...,n) or decreasing order (n, n-1, ..., 2). But careful: Since the circle orientation is fixed, we need to consider the order after 1 in clockwise direction. The clockwise direction is as given by p: p_1 -> p_2 -> ... -> p_n -> back to p_1. So if we locate index pos where p[pos] = 1, then moving clockwise means taking indices pos+1, pos+2, ... modulo n. Then we can read the sequence of numbers after 1. For clockwise round dance, after 1 we should see 2,3,...,n in that order. For counterclockwise round dance, after 1 we should see n, n-1, ..., 2 in that order (because from 1 going clockwise we encounter n, then n-1,...? Let's verify: In the counterclockwise valid cycle we derived, clockwise order from 1 is 1, n, n-1, ..., 2. So after 1 (clockwise) we see n, then n-1, ..., 2. So that is the pattern. So we can check both possibilities.
But also we must consider that the round dance could be started with clockwise direction, meaning the condition that i is after i-1 in clockwise order for all i. That means if we start at 1, going clockwise we see 2,3,...,n. So that pattern.
So algorithm: For each query, read n and array p[0..n-1].
Find index k such that p[k] == 1.
Let forward sequence: Starting from k+1 (mod n) and going through n-1 elements (i.e., all except the 1), collect the values in order: p[(k+1)%n], p[(k+2)%n], ..., p[(k+n-1)%n].
Check if this sequence equals [2,3,...,n] (i.e., strictly increasing by 1). If yes, print YES.
Else, check if this sequence equals [n, n-1, ..., 2] (i.e., strictly decreasing by 1). If yes, print YES.
Otherwise NO.
But is that sufficient? Consider edge cases: n=1. Then there is only one student with index 1. Both clockwise and counterclockwise conditions? For n=1, the conditions vacuously hold? Since there are no i from 2 to n, so both conditions are trivially true. So answer should be YES. Our method: find index of 1 (only element). The forward sequence after 1 would be empty (since n-1=0). So we compare empty list to [2..1] (empty) and to [n..2] (for n=1, that is empty). Both would be considered equal? Implementation wise, we need to treat n=1 as YES.
For n=2: Permutations [1,2] and [2,1] both should work? Let's test: For [1,2], clockwise: after 1 we have 2, so condition holds for clockwise (1->2). For counterclockwise: after 1 going clockwise we have 2, but we need after 1 we have n=2? Actually the counterclockwise pattern after 1 should be [2] (since n=2, sequence [2] is both increasing? Actually [2] is also equal to decreasing? It's just a single element, so both checks would succeed? But careful: For n=2, the counterclockwise valid cycle is [1,2] or [2,1]? Let's derive: Condition for counterclockwise: succ_cw(2)=1, succ_cw(1)=2. So clockwise order from 1: 1,2. That is actually same as the clockwise valid cycle. So both conditions are satisfied? Actually a round dance can be started either clockwise or counterclockwise; if the arrangement satisfies either, answer is YES. For [2,1], clockwise order from 1? Find 1 at position 2 (if p=[2,1]), after 1 clockwise: from p[1]=1, next is p[0] (since wrap) =2. So after 1 we get [2] which matches the increasing pattern? That would indicate clockwise condition holds? But check: For [2,1], is it true that student 2 comes right after student 1 in clockwise order? Student 1 is at position 2, its clockwise neighbor is 2 (since p[0] is 2 and after p[1] comes p[0]? Actually careful: p is given as clockwise order. So p[0]=2, p[1]=1. Then clockwise order: 2 -> 1 -> (back to 2). So student 1's clockwise neighbor is? Starting at student 1 (p[1]), the next clockwise is p[2]? But index 2 is out of range; wrap to p[0]=2. So indeed clockwise neighbor of 1 is 2. So student 2 is right after student 1 clockwise. That satisfies condition for i=2? But for clockwise round dance we need student 2 after student 1. That's satisfied. However, we also need student 3 after student 2, etc. There's only two, so yes. So [2,1] also satisfies clockwise condition? But wait, the clockwise condition requires that student 2 comes right after student 1 clockwise. That is true. So both [1,2] and [2,1] satisfy clockwise condition? Check [2,1]: student 1 is at position 1? Actually p=[2,1] means first student is 2, second is 1. Clockwise order: 2 then 1 then back to 2. So student 1's clockwise neighbor is 2? After 1 (the second) the next clockwise is back to first which is 2, so yes, 2 is after 1. So condition holds. But is it true that student 2 is right after student 1? Yes. So [2,1] qualifies for clockwise round dance. Similarly [1,2] qualifies. So for n=2, any permutation qualifies? Because the only two permutations are [1,2] and [2,1], both should be YES. Indeed our algorithm: For [1,2], after 1 we get [2] which matches increasing (since expected [2] is [2]) -> YES. For [2,1], find index of 1 at position 1, after 1 we get p[0]=2, which is [2] -> matches increasing -> YES. So both work.
But wait, is there any arrangement that is not a rotation of inc or dec but still satisfies? Possibly if we consider the condition is only that for each i from 2 to n, the immediate clockwise neighbor of i-1 is i. That essentially defines a permutation on the set of edges: a directed cycle where each i-1 points to i. That forces the cycle to be exactly (1,2,3,...,n) in clockwise direction. However, could it be that the cycle is, say, (2,3,4,...,n,1) but with a different labeling? Actually that's the same cycle just starting at 2. That is a rotation. So yes, it must be a rotation of inc. Similarly for ccw condition it must be a rotation of dec. So our check is correct.
But careful: The input gives p as a list representing clockwise order starting from some student. That starting student is arbitrary. Our method of finding 1 and then checking the sequence after it works: because if the circle is a rotation of inc, then starting at 1, the clockwise order should be 1,2,3,...,n. So after 1 we should see 2,3,...,n. That holds regardless of where 1 appears in the input list, as long as the cycle is correct. Because we locate 1 and then look at the order clockwise from there; if the circle is a rotation of inc, the sequence after 1 will be 2,3,...,n. If it's a rotation of dec, the sequence after 1 will be n,n-1,...,2. So our check is correct.
But what about the possibility that the circle is exactly inc but with 1 not at the start of p? That's fine; we locate it. So we only need to check the two patterns after 1.
But is it necessary to also consider the possibility that the round dance could be started in counterclockwise direction but the pattern after 1 might be something else? Let's double-check the translation: Counterclockwise round dance condition: For i from 2 to n, student i is right after student i-1 in counterclockwise order. That gives succ_cw(i) = i-1 for i>=2, and then succ_cw(1) must be n. So the clockwise order from 1 is: 1, n, n-1, ..., 2. So indeed after 1 clockwise we see n, n-1, ..., 2. So our check is correct.
But wait: Could the condition also be satisfied if the circle is reversed orientation? That is, if the students are arranged in increasing order but in counterclockwise direction? Actually the problem defines clockwise round dance and counterclockwise round dance separately. For clockwise round dance, they require that when moving clockwise, you see 1,2,3,... in order. For counterclockwise round dance, they require that when moving counterclockwise, you see 1,2,3,... in order. That is not the same as increasing order in counterclockwise direction being the reverse? Let's ensure: The description: "A counterclockwise round dance is almost the same thing — the only difference is that the student i should be right after the student i - 1 in counterclockwise order (this condition should be met for every i from 2 to n)." So it's the same condition but with direction reversed. So if we denote the circle order clockwise, then the condition for counterclockwise dance is as we derived. So indeed it's exactly that.
Therefore, algorithm is simple.
But wait: There might be a subtlety: The input p is given as the clockwise order, but we don't know which student is considered first? However, the input defines p_1 as the index of the i-th student (in clockwise order). So the order is fixed. That means the starting point for the list is some student. Our method uses the position of 1 and then looks forward in the array (mod n) to get clockwise order from 1. This respects the given orientation. So it's correct.
Now test with provided examples:
Example Input:
5 4 1 2 3 4 -> After 1: 2,3,4 matches inc -> YES 3 1 3 2 -> After 1: 3,2. inc? 3,2 is not 2,3. dec? For n=3, dec after 1 should be [3,2]? Indeed dec pattern: 1,3,2. After 1: 3,2 matches dec -> YES 5 1 2 3 5 4 -> After 1: 2,3,5,4. Compare inc: 2,3,4,5? Actually inc expects [2,3,4,5] but we have [2,3,5,4] -> not inc. dec expects [5,4,3,2]? Actually dec after 1 should be [5,4,3,2]? For n=5, dec: 1,5,4,3,2 => after 1: 5,4,3,2. Our after 1: 2,3,5,4 -> no. So NO. 1 1 -> After 1: empty, matches both? So YES. 5 3 2 1 5 4 -> Locate 1 at index 2 (0-based). After 1: [5,4,3,2]? Actually p = [3,2,1,5,4]; after 1: indices 3,4,0,1 => [5,4,3,2]. This matches dec for n=5: after 1 should be [5,4,3,2] -> YES.
Matches outputs: YES, YES, NO, YES, YES.
So solution is straightforward.
But let's double-check with some other cases: n=4, p=[4,3,2,1]. After 1? 1 is at index 3? Actually p=[4,3,2,1] -> 1 at last. After 1: wrap to start: [4,3,2] -> that is [4,3,2] which is not inc (2,3,4) and not dec (4,3,2?) Wait dec after 1 expects [4,3,2] for n=4: dec pattern: 1,4,3,2 => after 1: 4,3,2. So matches dec. So YES. Indeed is that valid for counterclockwise? Let's check: p=[4,3,2,1] clockwise order: 4->3->2->1->4. Is that a valid counterclockwise round dance? According to our derived condition, a valid ccw arrangement is a rotation of [1,4,3,2]. Rotations: start at 1: 1,4,3,2; start at 4: 4,3,2,1; start at 3: 3,2,1,4; start at 2: 2,1,4,3. So [4,3,2,1] is a rotation (starting at 4). So yes.
Another case: p=[2,1,3,4] n=4. After 1 at index 1, after 1: [3,4,2]? Actually p=[2,1,3,4]; after 1: indices 2,3,0 => [3,4,2]. Inc: [2,3,4] no; dec: [4,3,2] no. So NO. That seems correct? Check manually: Clockwise order: 2->1->3->4->2. For clockwise: need 2 after 1? Actually condition for clockwise: 2 after 1? Here 1's cw neighbor is 3, not 2. So fails. For counterclockwise: need succ_cw(2)=1? Actually condition for ccw: succ_cw(2)=1? Let's see: need ccw(i-1)=i, i.e., succ_cw(i)=i-1. For i=2, succ_cw(2)=1. But in this arrangement, cw neighbor of 2 is? p: start at 2, cw neighbor is 1? Actually clockwise order: 2 then 1 then 3 then 4 then back to 2. So cw neighbor of 2 is 1. So succ_cw(2)=1, good. For i=3, need succ_cw(3)=2. But cw neighbor of 3 is 4, not 2. So fails. So NO.
Thus algorithm works.
Edge Cases: n=200, q=200, trivial.
Implementation: For each query, read n, read list p. Find index of 1 (using list.index). Then generate the sequence after: For i in range(1,n): val = p[(pos+i)%n]. Check if this equals i+1 (for inc) or equals n-i+1? Actually if we want to check inc: after 1, the i-th element (1-indexed) should be i+1. So for offset j from 1 to n-1, check if p[(pos+j)%n] == j+1. For dec: after 1, the i-th element should be n - (i-1)? Actually dec pattern: after 1, the sequence is n, n-1, ..., 2. So for j=1, expect n; j=2 expect n-1; ... j=n-1 expect 2. That is: expected = n - (j - 1). Or expected = n+1 - j.
So we can check both with loops.
Alternatively, we could check by constructing the two ideal sequences after 1 and compare directly.
Complexities: O(n) per query.
Double-check: Are there any other valid patterns? For example, what about the identity pattern but reversed? That's covered by dec. What about if the circle is such that the clockwise order is a rotation of [1,2,...,n] or a rotation of [1,n,n-1,...,2]? That's all.
But is there a scenario where the circle could satisfy both clockwise and counterclockwise conditions? For n=1, trivially both. For n=2, both? Actually both conditions yield the same arrangement? For n=2, inc sequence: [1,2]; dec sequence: [1,2] as well because [1,2] is both inc and dec? Let's compute dec: [1, n, n-1,...,2] for n=2 gives [1,2]. So they coincide. So any arrangement that is a rotation of [1,2] is [1,2] or [2,1]? Rotation of [1,2] yields [1,2] and [2,1]. Rotation of [1,2] is same as rotation of dec because dec = [1,2]. So both are the same set. So it's fine.
For n=3, inc set = rotations of [1,2,3] = [1,2,3], [2,3,1], [3,1,2]. dec set = rotations of [1,3,2] = [1,3,2], [3,2,1], [2,1,3]. Are these distinct? Yes, they are different sets (except maybe for n=2 they coincide). So need to check both.
So algorithm stands.
Now, there is a nuance: The input gives p_1 as the first student in clockwise order. That means the list order is the clockwise order starting from that student. So the relative order around the circle is fixed. Our method uses that order to look at clockwise direction from 1. That is correct because we treat the list as circular.
Implementation details: Use Python. For each query:
def solve(): import sys data = sys.stdin.read().split() it = iter(data) q = int(next(it)) out = [] for _ in range(q): n = int(next(it)) p = [int(next(it)) for __ in range(n)] # find index of 1 pos = p.index(1) # check inc inc_ok = True for i in range(1, n): if p[(pos + i) % n] != i + 1: inc_ok = False break if inc_ok: out.append("YES") continue # check dec dec_ok = True for i in range(1, n): if p[(pos + i) % n] != n - i + 1: # for i=1, expect n; i=2 -> n-1; ... i=n-1 -> 2 dec_ok = False break if dec_ok: out.append("YES") else: out.append("NO") print("\n".join(out))
That should work.
But wait: What about the possibility that the round dance could be started in clockwise direction but the sequence after 1 is not exactly 2,3,...,n because the circle might be oriented differently? For clockwise round dance, condition is that 2 is after 1 clockwise, 3 after 2 clockwise, ..., n after n-1 clockwise. That doesn't require that 1 is the start of the sequence; but it does imply that if you start at 1 and go clockwise, you will see 2, then 3, then ... then n. Because from 1 you go to its immediate clockwise neighbor, which must be 2 (since 2 after 1). Then from 2 you go to its immediate clockwise neighbor, which must be 3, etc. So indeed the clockwise order from 1 is 1,2,3,...,n. So our method is correct.
Now, is there any scenario where the condition holds but the after-1 sequence is not exactly that because the circle might have 1 not at the position we think? Actually we locate 1 and then check clockwise from there. That exactly checks that condition.
But what if the condition holds but the direction is opposite? For example, suppose the circle is such that the clockwise order from 1 is not 2,3,...,n, but the counterclockwise order from 1 is 2,3,...,n, meaning that the clockwise order from 1 is something else? That would satisfy the counterclockwise condition, which we check via dec pattern. So it's covered.
Thus solution is correct.
But wait, there is an alternative perspective: The problem might be simpler: The only possible valid permutations are those where the absolute differences between consecutive elements (cyclic) are either 1 or n-1? Not exactly. But we can just implement as above.
Now, I'd like to double-check with some more examples: n=4, p=[2,3,4,1] -> After 1 at index 3, after 1: [2,3,4]? Actually p=[2,3,4,1], pos=3, after: indices 0,1,2 -> [2,3,4] matches inc? inc expects [2,3,4] -> YES. So that is a rotation of [1,2,3,4] starting at 2? Actually [2,3,4,1] is a rotation. Good.
n=4, p=[4,1,2,3] -> After 1 at index 1, after: [2,3,4] -> inc? [2,3,4] matches inc -> YES.
n=4, p=[3,4,1,2] -> After 1 at index 2, after: [2,3,4]? Actually p=[3,4,1,2]; pos=2; after: indices 3,0,1 -> [2,3,4] -> inc -> YES.
All these are rotations of inc.
n=4, p=[2,1,4,3] -> After 1 at index 1, after: [4,3,2]? Actually p=[2,1,4,3]; pos=1; after: indices 2,3,0 -> [4,3,2] -> dec? dec expects [4,3,2] -> YES. So it's a rotation of dec? Rotations of dec [1,4,3,2] are: [1,4,3,2], [4,3,2,1], [3,2,1,4], [2,1,4,3]. Indeed [2,1,4,3] is a rotation. Good.
Now, test a tricky one: n=5, p=[1,3,5,2,4] -> After 1: [3,5,2,4]. inc expects [2,3,4,5] no; dec expects [5,4,3,2] no. So NO.
Thus algorithm should be correct.
Time complexity: O(qn) which is up to 200200 = 40000, trivial.
Now, ensure to handle n=1 correctly: loop for i in range(1,n) will be empty, so inc_ok will be True (since no mismatches). Similarly dec_ok will be True. So we will output "YES". Good.
But careful: In Python, for i in range(1, n) when n=1, range(1,1) is empty, so inc_ok remains True. Then we output "YES". That's correct.
Now, consider if there is any pitfall: The input says "the i-th student (in clockwise order)". So p_i is the index of the i-th student. So the list order is clockwise. So our use of modulo for clockwise direction after 1 is correct: Starting from position pos (where p[pos]=1), the next clockwise is p[(pos+1)%n] then p[(pos+2)%n] etc.
Thus final solution as described.
We might also consider an alternative approach: Check if the array is such that the differences between consecutive elements (cyclic) are either 1 or (n-1)? Actually, for inc rotation, the differences (p[i+1] - p[i]) mod n = 1 (if we consider numbers modulo n, with 1..n). For dec rotation, the differences (p[i+1] - p[i]) mod n = -1 mod n = n-1. But careful: Because the numbers are from 1 to n, but modulo n we might treat them as 0..n-1. But the pattern after rotating might not be consistent if the start is not at 1? Let's examine: For inc rotation: the sequence is a cyclic shift of [1,2,...,n]. If we compute differences (p[(i+1)%n] - p[i]) mod n, we should get either 1 (for most) except one place where it wraps from n to next which is 1? Actually consider [2,3,4,1] -> differences: 2->3: 1; 3->4: 1; 4->1: (1-4) = -3 mod 4 = 1? If we consider modulo 4 with values 1..4, we can map to 0..3: 2->1,3->2,4->3,1->0 maybe? Not trivial. But we could also check by finding 1 and then verifying sequence. That's simpler.
Now, we must also consider whether the direction of the round dance could be satisfied if the sequence after 1 is increasing but not starting at 2? Actually after 1 it must be exactly 2,3,...,n in order. So that's strict.
Thus solution is done.
But wait: The problem statement: "Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student n comes right after the student n - 1 in clockwise order." This doesn't explicitly require that student 1 is somewhere; it's just a condition about the positions of all numbers relative to each other. Could there be a scenario where the cycle is such that 1 is not adjacent to 2? Actually condition says student 2 must be right after student 1 (clockwise). So they must be adjacent in that order. So 1 and 2 must be neighbors with 2 after 1 clockwise. That forces the relative positions. Similarly, 3 must be right after 2 clockwise, so 2 and 3 adjacent, etc. So it forces a chain 1-2-3-...-n in clockwise direction. Since there are n students, the chain must include all and then the circle closes with n adjacent to 1? Actually it does not require n to be adjacent to 1, but as argued, it's forced because after n there must be some neighbor; but if n's clockwise neighbor is not 1, then that neighbor would be some other student, but all students are already in the chain, so it must be 1. So indeed it's a cycle.
Thus our interpretation is correct.
Now, the problem may be from Codeforces Round #1611 (Div. 2) problem A? Actually it's problem "Round Dance" maybe from Codeforces Round #1832? Not sure. But anyway.
I will write final answer with explanation and code.
But before finalize, consider edge-case n=0? No n>=1.
Implementation details: Use input reading maybe faster.
Now, I'll produce final solution.
But also think: Could there be any valid arrangement where after 1 the sequence is [2,3,...,n] but not necessarily in that exact order because maybe the condition does not require that the numbers appear consecutively around the circle? Wait, the condition is that for each i from 2 to n, student i is immediately after student i-1 in clockwise order. So if we start at 1 and go clockwise, we must see 2 as the next, then 3 as the next, then 4, etc. So yes, it forces that exact order.
So final answer.
Now, produce final solution with code.
But also note: There is a simpler approach: after