Shinju and the Lost Permutation (Codeforces 1658C)
Tags: Math, constructive algorithms

Shinju loves permutations very much! Today, she has borrowed a permutation $$$p$$$ from Juju to play with.The $$$i$$$-th cyclic shift of a permutation $$$p$$$ is a transformation on the permutation such that $$$p = [p_1, p_2, \ldots, p_n] $$$ will now become $$$ p = [p_{n-i+1}, \ldots, p_n, p_1,p_2, \ldots, p_{n-i}]$$$.Let's define the power of permutation $$$p$$$ as the number of distinct elements in the prefix maximums array $$$b$$$ of the permutation. The prefix maximums array $$$b$$$ is the array of length $$$n$$$ such that $$$b_i = \max(p_1, p_2, \ldots, p_i)$$$. For example, the power of $$$[1, 2, 5, 4, 6, 3]$$$ is $$$4$$$ since $$$b=[1,2,5,5,6,6]$$$ and there are $$$4$$$ distinct elements in $$$b$$$.Unfortunately, Shinju has lost the permutation $$$p$$$! The only information she remembers is an array $$$c$$$, where $$$c_i$$$ is the power of the $$$(i-1)$$$-th cyclic shift of the permutation $$$p$$$. She's also not confident that she remembers it correctly, so she wants to know if her memory is good enough.Given the array $$$c$$$, determine if there exists a permutation $$$p$$$ that is consistent with $$$c$$$. You do not have to construct the permutation $$$p$$$.A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3, 4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^3$$$) — the number of test cases.The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \leq c_i \leq n$$$). It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print "YES" if there is a permutation $$$p$$$ exists that satisfies the array $$$c$$$, and "NO" otherwise.You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

Note: In the first test case, the permutation $$$[1]$$$ satisfies the array $$$c$$$.In the second test case, the permutation $$$[2,1]$$$ satisfies the array $$$c$$$.In the fifth test case, the permutation $$$[5, 1, 2, 4, 6, 3]$$$ satisfies the array $$$c$$$. Let's see why this is true.  The zeroth cyclic shift of $$$p$$$ is $$$[5, 1, 2, 4, 6, 3]$$$. Its power is $$$2$$$ since $$$b = [5, 5, 5, 5, 6, 6]$$$ and there are $$$2$$$ distinct elements — $$$5$$$ and $$$6$$$.  The first cyclic shift of $$$p$$$ is $$$[3, 5, 1, 2, 4, 6]$$$. Its power is $$$3$$$ since $$$b=[3,5,5,5,5,6]$$$.  The second cyclic shift of $$$p$$$ is $$$[6, 3, 5, 1, 2, 4]$$$. Its power is $$$1$$$ since $$$b=[6,6,6,6,6,6]$$$.  The third cyclic shift of $$$p$$$ is $$$[4, 6, 3, 5, 1, 2]$$$. Its power is $$$2$$$ since $$$b=[4,6,6,6,6,6]$$$.  The fourth cyclic shift of $$$p$$$ is $$$[2, 4, 6, 3, 5, 1]$$$. Its power is $$$3$$$ since $$$b = [2, 4, 6, 6, 6, 6]$$$.  The fifth cyclic shift of $$$p$$$ is $$$[1, 2, 4, 6, 3, 5]$$$. Its power is $$$4$$$ since $$$b = [1, 2, 4, 6, 6, 6]$$$. Therefore, $$$c = [2, 3, 1, 2, 3, 4]$$$.In the third, fourth, and sixth testcases, we can show that there is no permutation that satisfies array $$$c$$$.

Sample Inputs:
6
1
1
2
1 2
2
2 2
6
1 2 4 6 3 5
6
2 3 1 2 3 4
3
3 2 1

Sample Outputs:
YES
YES
NO
NO
YES
NO

Solution (Python):
def solve():
    if arr.count(1) != 1:
        return 'NO'
    for i in range(n - 1):
        if arr[i + 1] - arr[i] > 1:
            return 'NO'
    if arr[0] - arr[-1] > 1:
        return 'NO'
    return 'YES'
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
    n = int(input())
    arr = [int(x) for x in input().split()]
    print(solve())
''

Solution (Python):
import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    flag = 1
    for i in range(1, n):
        if a[i] - a[i - 1] > 1:
            flag = 0
            break
    if flag and a.count(1) == 1:
        if n > 1 and a[0] - a[-1] > 1:
            print('NO')
        else:
            print('YES')
    else:
        print('NO')

Solution (Python):
def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        c = [int(num) for num in input().split(' ')]
        if c.count(1) != 1:
            print('NO')
            continue
        no = False
        c.append(c[0])
        for i in range(1, n + 1):
            if c[i] - c[i - 1] > 1:
                no = True
                break
        print('NO' if no else 'YES')
if __name__ == '__main__':
    main()