[Solution] Shinju and the Lost Permutation solution codeforces

Shinju and the Lost Permutation solution codeforces – 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 𝑝=[𝑝1,𝑝2,,𝑝𝑛]p=[p1,p2,…,pn] will now become 𝑝=[𝑝𝑛𝑖+1,,𝑝𝑛,𝑝1,𝑝2,,𝑝𝑛𝑖]p=[pn−i+1,…,pn,p1,p2,…,pn−i].

Shinju and the Lost Permutation solution codeforces

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 𝑏𝑖=max(𝑝1,𝑝2,,𝑝𝑖)bi=max(p1,p2,…,pi). For example, the power of [1,2,5,4,6,3][1,2,5,4,6,3] is 44 since 𝑏=[1,2,5,5,6,6]b=[1,2,5,5,6,6] and there are 44 distinct elements in 𝑏b.

Unfortunately, Shinju has lost the permutation 𝑝p! The only information she remembers is an array 𝑐c, where 𝑐𝑖ci is the power of the (𝑖1)(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 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

Shinju and the Lost Permutation solution codeforces

The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡51031≤t≤5⋅103) — the number of test cases.

The first line of each test case contains an integer 𝑛n (1𝑛1051≤n≤105).

The second line of each test case contains 𝑛n integers 𝑐1,𝑐2,,𝑐𝑛c1,c2,…,cn (1𝑐𝑖𝑛1≤ci≤n).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

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).

Example
input

Copy
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

Shinju and the Lost Permutation solution codeforces

output

Copy
YES
YES
NO
NO
YES
NO

Shinju and the Lost Permutation solution codeforces Note

In the first test case, the permutation [1][1] satisfies the array 𝑐c.

In the second test case, the permutation [2,1][2,1] satisfies the array 𝑐c.

In the fifth test case, the permutation [5,1,2,4,6,3][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][5,1,2,4,6,3]. Its power is 22 since 𝑏=[5,5,5,5,6,6]b=[5,5,5,5,6,6] and there are 22 distinct elements — 55 and 66.
  • The first cyclic shift of 𝑝p is [3,5,1,2,4,6][3,5,1,2,4,6]. Its power is 33 since 𝑏=[3,5,5,5,5,6]b=[3,5,5,5,5,6].
  • The second cyclic shift of 𝑝p is [6,3,5,1,2,4][6,3,5,1,2,4]. Its power is 11 since 𝑏=[6,6,6,6,6,6]b=[6,6,6,6,6,6].
  • The third cyclic shift of 𝑝p is [4,6,3,5,1,2][4,6,3,5,1,2]. Its power is 22 since 𝑏=[4,6,6,6,6,6]b=[4,6,6,6,6,6].
  • The fourth cyclic shift of 𝑝p is [2,4,6,3,5,1][2,4,6,3,5,1]. Its power is 33 since 𝑏=[2,4,6,6,6,6]b=[2,4,6,6,6,6].
  • The fifth cyclic shift of 𝑝p is [1,2,4,6,3,5][1,2,4,6,3,5]. Its power is 44 since 𝑏=[1,2,4,6,6,6]b=[1,2,4,6,6,6].

Therefore, 𝑐=[2,3,1,2,3,4]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.

For Solution

Click Here

Leave a Comment