版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "比赛记录 - Codeforces Round #842 (Div. 2)" date: 2023-01-06 20:11:31 categories:

• 算法竞赛 tags:
• 算法竞赛
• Codeforces
• 贪心
• 数学
• 代数
• 置换
• 对换
• 组合数学
• 计数
• 数论
• 构造
• 模拟
• 图论
• DP
• 分块

比赛链接

进度: 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

4
3
6
8
10

output

2
5
7
9

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$

代码参考

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_{i1}, p{i2}, \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

4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4

output

0
1
1
2

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}]$

代码参考

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

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

output

YES
1
1
YES
1 3 4 2 5
5 2 3 1 4
NO

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

代码参考

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

Example

input

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

output

0
1
3
1

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

代码参考

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 100009067

output

9

input

2 100000357

output

1689

input

69 999900997

output

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$

代码参考

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(ai, 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

3
2 1 3

output

0 1 2

input

6
1 4 1 6 3 2

output

0 1 2 3 6 8

input

2
1 2

output

0 1

input

4
1 4 4 4

output

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$

代码参考