Flipper solution codeforces

Flipper solution codeforces

You are given a permutation 𝑝 of length 𝑛.

A permutation is an array consisting of 𝑛 distinct integers from 11 to 𝑛 in any order. For example, {2,3,1,5,4}{2,3,1,5,4} is a permutation, while {1,2,2}{1,2,2} is not (since 22 appears twice), and {1,3,4}{1,3,4} is also not a permutation (as 𝑛=3�=3, but the array contains 44).

To the permutation 𝑝, you need to apply the following operation exactly once:

• First you choose a segment [𝑙,𝑟][�,�] (1𝑙𝑟𝑛1≤�≤�≤�, a segment is a continuous sequence of numbers {𝑝𝑙,𝑝𝑙+1,,𝑝𝑟1,𝑝𝑟}{��,��+1,…,��−1,��}) and reverse it. Reversing a segment means swapping pairs of numbers (𝑝𝑙,𝑝𝑟)(��,��)(𝑝𝑙+1,𝑝𝑟1)(��+1,��−1), …, (𝑝𝑙+𝑖,𝑝𝑟𝑖)(��+�,��−�) (where 𝑙+𝑖𝑟𝑖�+�≤�−�).
• Then you swap the prefix and suffix: [𝑟+1,𝑛][�+1,�] and [1,𝑙1][1,�−1] (note that these segments may be empty).

For example, given 𝑛=5,𝑝={2,3,1,5,4}�=5,�={2,3,1,5,4}, if you choose the segment [𝑙=2,𝑟=3][�=2,�=3], after reversing the segment 𝑝={2,1,3,5,4}�={2,1,3,5,4}, then you swap the segments [4,5][4,5] and [1,1][1,1]. Thus, 𝑝={5,4,1,3,2}�={5,4,1,3,2}. It can be shown that this is the maximum possible result for the given permutation.

You need to output the lexicographically maximum permutation that can be obtained by applying the operation described exactly once.

A permutation 𝑎 is lexicographically greater than permutation 𝑏 if there exists an 𝑖 (1𝑖𝑛1≤�≤�) such that 𝑎𝑗=𝑏𝑗��=�� for 1𝑗<𝑖1≤�<� and 𝑎𝑖>𝑏𝑖��>��.

Flipper solution codeforces

The first line of the input contains a single integer 𝑡 (1𝑡10001≤�≤1000) — the number of test cases.

Then the descriptions of the test cases follow.

The first line of each test case contains a single integer 𝑛 (1𝑛20001≤�≤2000) — the size of the permutation.

The second line of each test case contains 𝑛 integers: 𝑝1,𝑝2,,𝑝𝑛�1,�2,…,�� (1𝑝𝑖𝑛1≤��≤�) — the permutation 𝑝 itself.

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

Output

For each test case, output in a separate line the lexicographically maximum permutation of length 𝑛 that can be obtained from 𝑝 by applying the operation described in the problem exactly once.

Example
input

Copy
9
5
2 3 1 5 4
9
4 1 6 7 2 8 5 3 9
4
4 3 2 1
2
2 1
6
3 2 4 1 5 6
7
3 2 1 5 7 6 4
10
10 2 5 6 1 9 3 8 4 7
4
4 2 1 3
1
1
output

Copy
5 4 1 3 2
9 4 1 6 7 2 8 5 3
3 2 1 4
1 2
6 5 3 2 4 1
7 6 4 5 3 2 1
9 3 8 4 7 1 10 2 5 6
3 4 2 1
1

Note

The first example is explained in the problem statement.

In the second example, the segment [𝑙=9,𝑟=9][�=9,�=9] should be chosen.

In the third example, the segment [𝑙=1,𝑟=1][�=1,�=1] should be chosen.

In the fourth example, the segment [𝑙=1,𝑟=2][�=1,�=2] should be chosen.

In the fifth example, the segment [𝑙=5,𝑟=6][�=5,�=6] should be chosen.

In the sixth example, the segment [𝑙=4,𝑟=4][�=4,�=4] should be chosen.

In the seventh example, the segment [𝑙=5,𝑟=5][�=5,�=5] should be chosen.