[Solution] Reverse solution codeforces

Reverse solution codeforces – You are given a permutation 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn of length 𝑛n. You have to choose two integers 𝑙,𝑟l,r (1𝑙𝑟𝑛1≤l≤r≤n) and reverse the subsegment [𝑙,𝑟][l,r] of the permutation. The permutation will become 𝑝1,𝑝2,,𝑝𝑙1,𝑝𝑟,𝑝𝑟1,,𝑝𝑙,𝑝𝑟+1,𝑝𝑟+2,,𝑝𝑛p1,p2,…,pl−1,pr,pr−1,…,pl,pr+1,pr+2,…,pn.

Find the lexicographically smallest permutation that can be obtained by performing exactly one reverse operation on the initial permutation.

Note that for two distinct permutations of equal length 𝑎a and 𝑏b𝑎a is lexicographically smaller than 𝑏b if at the first position they differ, 𝑎a has the smaller element.

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

Reverse solution codeforces

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡5001≤t≤500) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛5001≤n≤500) — the length of the permutation.

The second line of each test case contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n) — the elements of the permutation.

Output

For each test case print the lexicographically smallest permutation you can obtain.

Reverse solution codeforces

4
1
1
3
2 1 3
4
1 4 2 3
5
1 2 3 4 5
output

Copy
1 
1 2 3 
1 2 4 3 
1 2 3 4 5 

Reverse solution codeforces

In the first test case, the permutation has length 11, so the only possible segment is [1,1][1,1]. The resulting permutation is [1][1].

In the second test case, we can obtain the identity permutation by reversing the segment [1,2][1,2]. The resulting permutation is [1,2,3][1,2,3].

In the third test case, the best possible segment is [2,3][2,3]. The resulting permutation is [1,2,4,3][1,2,4,3].

In the fourth test case, there is no lexicographically smaller permutation, so we can leave it unchanged by choosing the segment [1,1][1,1]. The resulting permutation is [1,2,3,4,5][1,2,3,4,5].

Leave a Comment