# 比赛记录 - Codeforces Round #842 (Div. 2)

进度: 6 / 6

## 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\)

### Example

#### input

1 | 4 |

#### output

1 | 2 |

### 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

1 | /* |

## 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

### Example

#### input

1 | 4 |

#### output

1 | 0 |

### 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

1 | /* |

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

### Example

#### input

1 | 3 |

#### output

1 | YES |

### 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

1 | /* |

## 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 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

### Example

#### input

1 | 4 |

#### output

1 | 0 |

### 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

1 | /* |

## 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\)

### Examples

#### input

1 | 1 100009067 |

#### output

1 | 9 |

#### input

1 | 2 100000357 |

#### output

1 | 1689 |

#### input

1 | 69 999900997 |

#### output

1 | 193862705 |

### 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

1 | /* |

## 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\)

### Examples

#### input

1 | 3 |

#### output

1 | 0 1 2 |

#### input

1 | 6 |

#### output

1 | 0 1 2 3 6 8 |

#### input

1 | 2 |

#### output

1 | 0 1 |

#### input

1 | 4 |

#### output

1 | 0 1 4 8 |

### 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

1 | /* |