## A - Greatest Convex

You are given an integer $$k$$. Find the largest integer $$x$$, where $$1 \le x < k$$, such that $$x! + (x - 1)!^\dagger$$ is a multiple of $$^\ddagger$$ $$k$$, or determine that no such $$x$$ exists

$$^\dagger$$ $$y!$$ denotes the factorial of $$y$$, which is defined recursively as $$y! = y \cdot (y-1)!$$ for $$y \geq 1$$ with the base case of $$0! = 1$$. For example, $$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120$$

$$^\ddagger$$ If $$a$$ and $$b$$ are integers, then $$a$$ is a multiple of $$b$$ if there exists an integer $$c$$ such that $$a = b \cdot c$$. For example, $$10$$ is a multiple of $$5$$ but $$9$$ is not a multiple of $$6$$

### Input

The first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The only line of each test case contains a single integer $$k$$ ($$2 \le k \le 10^9$$)

### Output

For each test case output a single integer — the largest possible integer $$x$$ that satisfies the conditions above

If no such $$x$$ exists, output $$-1$$

### Note

In the first test case, $$2! + 1! = 2 + 1 = 3$$, which is a multiple of $$3$$

In the third test case, $$7! + 6! = 5040 + 720 = 5760$$, which is a multiple of $$8$$

Show code

## B - Quick Sort

You are given a permutation$$^\dagger$$ $$p$$ of length $$n$$ and a positive integer $$k \le n$$

In one operation, you:

• Choose $$k$$ distinct elements $$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$$
• Remove them and then add them sorted in increasing order to the end of the permutation

For example, if $$p = [2,5,1,3,4]$$ and $$k = 2$$ and you choose $$5$$ and $$3$$ as the elements for the operation, then $$[2, {\color{red}5}, 1, {\color{red}3}, 4] \rightarrow [2, 1, 4, {\color{red}3},{\color{red}5}]$$

Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven that it is always possible to do so

$$^\dagger$$ A permutation of length $$n$$ 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 first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The first line of each test case contains two integers $$n$$ and $$k$$ ($$2 \le n \le 10^5$$, $$1 \le k \le n$$)

The second line of each test case contains $$n$$ integers $$p_1,p_2,\ldots, p_n$$ ($$1 \le p_i \le n$$). It is guaranteed that $$p$$ is a permutation

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$10^5$$

### Output

For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so

### Note

In the first test case, the permutation is already sorted

In the second test case, you can choose element $$3$$, and the permutation will become sorted as follows: $$[{\color{red}3}, 1, 2] \rightarrow [1, 2, {\color{red}3}]$$

In the third test case, you can choose elements $$3$$ and $$4$$, and the permutation will become sorted as follows: $$[1, {\color{red}3}, 2, {\color{red}4}] \rightarrow [1, 2, {\color{red}3},{\color{red}4}]$$

In the fourth test case, it can be shown that it is impossible to sort the permutation in $$1$$ operation. However, if you choose elements $$2$$ and $$1$$ in the first operation, and choose elements $$3$$ and $$4$$ in the second operation, the permutation will become sorted as follows: $$[{\color{red}2}, 3, {\color{red}1}, 4] \rightarrow [{\color{blue}3}, {\color{blue}4}, {\color{red}1}, {\color{red}2}] \rightarrow [1,2, {\color{blue}3}, {\color{blue}4}]$$

Show code

## C - Elemental Decompress

You are given an array $$a$$ of $$n$$ integers

Find two permutations$$^\dagger$$ $$p$$ and $$q$$ of length $$n$$ such that $$\max(p_i,q_i)=a_i$$ for all $$1 \leq i \leq n$$ or report that such $$p$$ and $$q$$ do not exist

$$^\dagger$$ A permutation of length $$n$$ 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 first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ ($$1 \le n \le 2 \cdot 10^5$$)

The second line of each test case contains $$n$$ integers $$a_1,a_2,\ldots,a_n$$ ($$1 \leq a_i \leq n$$) — the array $$a$$

It is guaranteed that the total sum of $$n$$ over all test cases does not exceed $$2 \cdot 10^5$$

### Output

For each test case, if there do not exist $$p$$ and $$q$$ that satisfy the conditions, output "NO" (without quotes)

Otherwise, output "YES" (without quotes) and then output $$2$$ lines. The first line should contain $$n$$ integers $$p_1,p_2,\ldots,p_n$$ and the second line should contain $$n$$ integers $$q_1,q_2,\ldots,q_n$$

If there are multiple solutions, you may output any of them

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response)

### Note

In the first test case, $$p=q=[1]$$. It is correct since $$a_1 = max(p_1,q_1) = 1$$

In the second test case, $$p=[1,3,4,2,5]$$ and $$q=[5,2,3,1,4]$$. It is correct since:

• $$a_1 = \max(p_1, q_1) = \max(1, 5) = 5$$,
• $$a_2 = \max(p_2, q_2) = \max(3, 2) = 3$$,
• $$a_3 = \max(p_3, q_3) = \max(4, 3) = 4$$,
• $$a_4 = \max(p_4, q_4) = \max(2, 1) = 2$$,
• $$a_5 = \max(p_5, q_5) = \max(5, 4) = 5$$

In the third test case, one can show that no such $$p$$ and $$q$$ exist

Show code

## D - Lucky Permutation

You are given a permutation$$^\dagger$$ $$p$$ of length $$n$$

In one operation, you can choose two indices $$1 \le i < j \le n$$ and swap $$p_i$$ with $$p_j$$

Find the minimum number of operations needed to have exactly one inversion$$^\ddagger$$ in the permutation

$$^\dagger$$ 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)

$$^\ddagger$$ The number of inversions of a permutation $$p$$ is the number of pairs of indices $$(i, j)$$ such that $$1 \le i < j \le n$$ and $$p_i > p_j$$

### Input

The first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ ($$2 \le n \le 2 \cdot 10^5$$)

The second line of each test case contains $$n$$ integers $$p_1,p_2,\ldots, p_n$$ ($$1 \le p_i \le n$$). It is guaranteed that $$p$$ is a permutation

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$2 \cdot 10^5$$

### Output

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists

### Note

In the first test case, the permutation already satisfies the condition

In the second test case, you can perform the operation with $$(i,j)=(1,2)$$, after that the permutation will be $$[2,1]$$ which has exactly one inversion

In the third test case, it is not possible to satisfy the condition with less than $$3$$ operations. However, if we perform $$3$$ operations with $$(i,j)$$ being $$(1,3)$$,$$(2,4)$$, and $$(3,4)$$ in that order, the final permutation will be $$[1, 2, 4, 3]$$ which has exactly one inversion

In the fourth test case, you can perform the operation with $$(i,j)=(2,4)$$, after that the permutation will be $$[2,1,3,4]$$ which has exactly one inversion

Show code

## E - Partial Sorting

Consider a permutation$$^\dagger$$ $$p$$ of length $$3n$$. Each time you can do one of the following operations:

• Sort the first $$2n$$ elements in increasing order
• Sort the last $$2n$$ elements in increasing order

We can show that every permutation can be made sorted in increasing order using only these operations. Let's call $$f(p)$$ the minimum number of these operations needed to make the permutation $$p$$ sorted in increasing order

Given $$n$$, find the sum of $$f(p)$$ over all $$(3n)!$$ permutations $$p$$ of size $$3n$$

Since the answer could be very large, output it modulo a prime $$M$$

$$^\dagger$$ A permutation of length $$n$$ 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 only line of input contains two numbers $$n$$ and $$M$$ ($$1 \leq n \leq 10^6$$, $$10^8 \leq M \leq 10^9$$). It is guaranteed that $$M$$ is a prime number

### Output

Output the answer modulo $$M$$

### Note

In the first test case, all the permutations are:

• $$[1, 2, 3]$$, which requires $$0$$ operations;
• $$[1, 3, 2]$$, which requires $$1$$ operation;
• $$[2, 1, 3]$$, which requires $$1$$ operation;
• $$[2, 3, 1]$$, which requires $$2$$ operations;
• $$[3, 1, 2]$$, which requires $$2$$ operations;
• $$[3, 2, 1]$$, which requires $$3$$ operations

Therefore, the answer is $$0+1+1+2+2+3=9$$

Show code

## F - Wonderful Jump

You are given an array of positive integers $$a_1,a_2,\ldots,a_n$$ of length $$n$$

In one operation you can jump from index $$i$$ to index $$j$$ ($$1 \le i \le j \le n$$) by paying $$\min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2$$ eris

For all $$k$$ from $$1$$ to $$n$$, find the minimum number of eris needed to get from index $$1$$ to index $$k$$

### Input

The first line contains a single integer $$n$$ ($$2 \le n \le 4 \cdot 10^5$$)

The second line contains $$n$$ integers $$a_1,a_2,\ldots a_n$$ ($$1 \le a_i \le n$$)

### Output

Output $$n$$ integers — the $$k$$-th integer is the minimum number of eris needed to reach index $$k$$ if you start from index $$1$$

### Note

In the first example:

• From $$1$$ to $$1$$: the cost is $$0$$,
• From $$1$$ to $$2$$: $$1 \rightarrow 2$$ — the cost is $$\min(2, 1) \cdot (2 - 1) ^ 2=1$$,
• From $$1$$ to $$3$$: $$1 \rightarrow 2 \rightarrow 3$$ — the cost is $$\min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2$$

In the fourth example from $$1$$ to $$4$$: $$1 \rightarrow 3 \rightarrow 4$$ — the cost is $$\min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8$$

Show code