Codeforces Round 1121 (Div. 2)
A. Rumb Needs a Hand
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Rumb visits a prosthetist because his arms have gone numb. The prosthetist can assemble replacements, but their numbered components are out of order. Apparently, even getting a helping hand requires some assembly.

Formally, the labels on the components form a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$. Mr. Rumb can program a machine to perform the following operation exactly once:

  • choose an integer $$$m$$$ ($$$1 \le m \le n$$$) and indices $$$i_1 \lt i_2 \lt \ldots \lt i_m$$$;
  • reverse the elements of $$$p$$$ at the chosen indices. More precisely, for every $$$j$$$ from $$$1$$$ to $$$m$$$, the element at index $$$i_j$$$ moves to index $$$i_{m-j+1}$$$. All other elements remain unchanged.

The chosen indices do not have to be consecutive. For example, suppose $$$p = [1, {\color{red}{6}}, 3, {\color{red}{4}}, 5, {\color{red}{2}}]$$$. If you choose indices $$$2$$$, $$$4$$$, and $$$6$$$, the elements shown in red are reversed, and $$$p$$$ becomes $$$[1, {\color{red}{2}}, 3, {\color{red}{4}}, 5, {\color{red}{6}}]$$$.

Determine whether Mr. Rumb can sort $$$p$$$ in increasing order.

$$$^{\text{∗}}$$$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

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line contains a permutation $$$p_1, p_2, \ldots, p_n$$$ of the integers from $$$1$$$ to $$$n$$$.

Output

For each test case, output YES if it is possible to sort $$$p$$$ in increasing order after performing exactly one operation. Otherwise, output NO.

You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Example
Input
5
1
1
4
4 2 3 1
4
3 4 1 2
5
2 1 3 5 4
6
1 6 3 4 5 2
Output
YES
YES
NO
NO
YES
Note

In the first test case, choose the only index. Reversing a single element does not change the permutation, so the requirement to perform exactly one operation is satisfied.

In the second test case, choose indices $$$1$$$ and $$$4$$$. The resulting permutation is $$$[1, 2, 3, 4]$$$.

In the fifth test case, choose indices $$$2$$$, $$$4$$$, and $$$6$$$. Notice that the chosen indices are not consecutive.

B. Knife's Pill Farm
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Knife has drafted $$$n$$$ absurd posts for a channel on a chat platform. His goal is to farm pill emoji reactions. Unfortunately, the channel's pill-farming bot uses an unnecessarily elaborate scoring rule.

The drafts have absurdity ratings $$$a_1, a_2, \ldots, a_n$$$, which may be negative. Mr. Knife must publish exactly $$$m$$$ drafts in their original order. Their ratings form a subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$ with length $$$m$$$.

His pill score starts at $$$0$$$. When he publishes the $$$i$$$-th chosen draft, the bot changes his score by $$$i \cdot (b_i - b_{i-1})$$$, where $$$b_0 = 0$$$. A negative change deducts points, and the score is allowed to become negative. Thus, his final pill score is $$$$$$ \sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}). $$$$$$

What is the maximum pill score Mr. Knife can obtain by choosing which drafts to publish?

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — the number of drafts and the number of posts Mr. Knife must publish.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^7 \le a_i \le 10^7$$$) — the absurdity ratings of the drafts.

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

Output

For each test case, print one integer — the maximum pill score Mr. Knife can obtain by publishing exactly $$$m$$$ drafts in their original order.

Example
Input
6
5 3
0 8 1 7 3
4 3
0 -4 10 -2
4 2
0 5 -2 4
6 3
0 9 8 7 6 5
1 1
7
3 2
5 -100 4
Output
20
34
10
15
7
108
Note

In the first test case, Mr. Knife can publish the drafts with ratings $$$[0, 1, 7]$$$. His final pill score is $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20. $$$$$$

In the second test case, he can publish the drafts with ratings $$$[0, -4, 10]$$$. The second post deducts points, but the third post more than makes up for it. His final pill score is $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34. $$$$$$

C. Madamant's Skating Dynasty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Madam Madamant is expecting a baby and already planning a skating dynasty in which every parent is a stronger skater than their children.

Formally, Madamant has $$$n$$$ labeled skaters. Skater $$$v$$$ has an integer rating $$$a_v$$$, and all ratings are pairwise distinct. A possible dynasty is represented by a rooted tree on these skaters.

Let $$$r$$$ be the root of the tree. For every skater $$$v \ne r$$$, let $$$p_v$$$ be the parent of $$$v$$$. The dynasty is valid if $$$a_v \lt a_{p_v}$$$ for every $$$v \ne r$$$.

The cost of a valid dynasty is $$$$$$ \sum_{v \ne r} (a_{p_v} - a_v). $$$$$$

Two dynasties are different if their roots are different or if the parent of at least one skater is different.

Find the sum of the costs of all valid dynasties Madamant can form, modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — their ratings.

It is guaranteed that all $$$a_i$$$ are pairwise distinct.

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

Output

For each test case, print one integer — the sum of the costs of all valid dynasties, modulo $$$998\,244\,353$$$.

Example
Input
5
1
10
3
1 2 3
4
4 1 3 2
2
1 1000000000
5
2 7 1 10 4
Output
0
5
27
1755646
414
Note

In the second test case, the skater with rating $$$3$$$ must be the root. The parent of the skater with rating $$$2$$$ must be the skater with rating $$$3$$$, while the skater with rating $$$1$$$ can choose either of the other skaters as their parent. The two valid dynasties have costs $$$2$$$ and $$$3$$$, so the answer is $$$5$$$.

In the fourth test case, there is only one valid dynasty. Its cost is $$$10^9 - 1 = 999\,999\,999$$$, whose remainder modulo $$$998\,244\,353$$$ is $$$1\,755\,646$$$.

D. Dr. Agos's Dark Mode
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Someone has chopped up Dr. Agos's chickens. Furious, he turns to the one thing that still brings him comfort: his OLED screen. Today, he wants almost all of it black.

The screen has a single row of $$$n$$$ pixels. Its pattern is represented by a binary string $$$s$$$; $$$s_i = 0$$$ means that the $$$i$$$-th pixel is dark, and $$$s_i = 1$$$ means that it is lit.

Dr. Agos finds a contiguous segment of pixels irritating if, when read from left to right as a binary integer, its value is divisible by $$$3$$$. More precisely, the segment from position $$$l$$$ to position $$$r$$$ ($$$1 \le l \le r \le n$$$) has value $$$$$$ \sum_{i=l}^{r} s_i \cdot 2^{r-i}. $$$$$$ Leading zeroes are allowed. A segment consisting only of dark pixels has value $$$0$$$, which is also divisible by $$$3$$$.

Let $$$f(s)$$$ be the number of irritating segments. Segments with different pairs of endpoints $$$(l,r)$$$ are counted separately, even if their pixel patterns are identical.

Dr. Agos wants a pattern with at most three lit pixels that minimizes $$$f(s)$$$ among all binary strings of length $$$n$$$, including strings with more than three ones. Help him construct such a pattern.

We can show that an answer always exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of pixels in the row.

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

Output

For each test case, print a binary string $$$s$$$ of length $$$n$$$ describing Dr. Agos's screen. It must contain at most three ones and minimize $$$f(s)$$$ among all binary strings of length $$$n$$$.

If there are multiple solutions, print any of them.

Example
Input
6
1
2
3
4
5
6
Output
1
11
101
0101
10101
010100
Note

For $$$n=1$$$, Dr. Agos can light the only pixel, giving $$$s=\mathtt{1}$$$. The only segment has value $$$1$$$, so it is not irritating and $$$f(s)=0$$$.

For $$$n=2$$$, he can light both pixels, giving $$$s=\mathtt{11}$$$. The whole row has binary value $$$3$$$ and is irritating, while each individual pixel has value $$$1$$$. Thus, $$$f(s)=1$$$. Every binary string of length $$$2$$$ has at least one irritating segment, so this is optimal.

The displayed patterns are not necessarily unique.

E1. A Prime Flood (Easy Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the Easy version of the problem. The difference between the versions is that in this version, $$$1 \le n \le 3000$$$. You can hack only if you solved all versions of this problem.

Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.

Formally, the initial water levels are given by an array $$$a = [a_1, a_2, \ldots, a_n]$$$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$. They may perform the following operation on $$$b$$$ any number of times, possibly zero:

  • choose a prime number $$$p$$$;
  • simultaneously decrease every element $$$b_i$$$ whose current value is divisible by $$$p$$$ by $$$1$$$. All other elements remain unchanged.

Let $$$f(b)$$$ be the maximum integer $$$x$$$ such that, after some sequence of operations, every element of $$$b$$$ is equal to $$$x$$$.

Find the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.

Each subsequence is considered independently, starting from its original values.

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3000$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, print one integer — the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$.

Example
Input
4
1
1
4
2 4 4 4
4
2 3 4 4
6
3 6 1 1 1 1
Output
1
37
34
72
Note

In the first test case, the only non-empty subsequence is $$$[1]$$$, and no operation is needed. Therefore, its contribution is $$$f([1]) = 1$$$.

In the second test case, the $$$2^3 - 1 = 7$$$ non-empty subsequences containing only occurrences of $$$4$$$ contribute $$$4 \cdot 7 = 28$$$. The subsequence $$$[2]$$$ contributes $$$2$$$. Each of the $$$7$$$ subsequences containing the value $$$2$$$ and at least one occurrence of $$$4$$$ has $$$f(b) = 1$$$. Hence, the answer is $$$28 + 2 + 7 = 37$$$.

E2. A Prime Flood (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the Hard version of the problem. The difference between the versions is that in this version, $$$n \le 3\cdot 10^5$$$. You can hack only if you solved all versions of this problem.

Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.

Formally, the initial water levels are given by an array $$$a = [a_1, a_2, \ldots, a_n]$$$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$. They may perform the following operation on $$$b$$$ any number of times, possibly zero:

  • choose a prime number $$$p$$$;
  • simultaneously decrease every element $$$b_i$$$ whose current value is divisible by $$$p$$$ by $$$1$$$. All other elements remain unchanged.

Let $$$f(b)$$$ be the maximum integer $$$x$$$ such that, after some sequence of operations, every element of $$$b$$$ is equal to $$$x$$$.

Find the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.

Each subsequence is considered independently, starting from its original values.

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.

Output

For each test case, print one integer — the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$.

Example
Input
4
1
1
4
2 4 4 4
4
2 3 4 4
6
3 6 1 1 1 1
Output
1
37
34
72
Note

In the first test case, the only non-empty subsequence is $$$[1]$$$, and no operation is needed. Therefore, its contribution is $$$f([1]) = 1$$$.

In the second test case, the $$$2^3 - 1 = 7$$$ non-empty subsequences containing only occurrences of $$$4$$$ contribute $$$4 \cdot 7 = 28$$$. The subsequence $$$[2]$$$ contributes $$$2$$$. Each of the $$$7$$$ subsequences containing the value $$$2$$$ and at least one occurrence of $$$4$$$ has $$$f(b) = 1$$$. Hence, the answer is $$$28 + 2 + 7 = 37$$$.

F. Deranged Calculator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hacks are disabled on this problem.

We are excited to introduce a new language for this Codeforces round: the Deranged Calculator language (DC).

The DC language is a simplified programming language with some weird constraints. It only supports a single expression on one line and only has a single positive integer $$$n$$$ as input. The syntax of the expression is similar to that of most programming languages (in fact, the expression is valid Python), but it is very limited:

  • Expressions consist of the input parameter $$$n$$$, parenthesized expressions, and calls to the round function. These are joined together by the operators +, -, *, and /.
  • Grouping with parentheses () can be used to change the order of operations, as usual.
  • The operators * and / have equal precedence and take precedence over + and -, which also have equal precedence. Operators of equal precedence are evaluated from left to right.
  • The round function takes a single expression as its argument and rounds its value to the nearest integer, rounding up when the fractional part is exactly $$$0.5$$$. (For example, round(n/(n-n-n-n)) will always evaluate to $$$0$$$, because $$$x/(x-x-x-x)=-\frac{1}{2}$$$ for a positive integer $$$x$$$. The fractional part is $$$0.5$$$, so it will be rounded up to $$$0$$$.)
  • Only the input value $$$n$$$ can be used; no numeric constants are allowed in the program.
  • All operations are performed using exact fractional arithmetic, so division does not round and can produce fractions.

A derangement of $$$n$$$ numbers is a permutation of those numbers in which none of the numbers appears in its original position. For example, the derangements of the sequence $$$[1, 2, 3]$$$ are $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$.

You are given a single integer $$$k$$$. Your job is to make a valid DC program that, for every integer $$$n$$$ ($$$2 \le n \le k$$$), calculates the number of derangements of the sequence $$$[1, 2, \ldots, n]$$$, when $$$n$$$ is given as input to the DC program. The length of the program should not exceed $$$10\,000$$$ characters.

A local testing tool is provided to help you develop your solution. It can be found under Contest Materials.

Input

The only line of input contains a single integer $$$k$$$ ($$$k \in \{2,3,50\}$$$).

Your DC program should output the correct number of derangements for all integers $$$n$$$ such that $$$2 \le n \le k$$$.

Output

Output a valid DC expression on a single line. The expression should only consist of the characters round()+-*/ and the length of the expression should not exceed $$$10\,000$$$ characters.

Your expression will be run on all integers $$$n$$$ such that $$$2 \le n \le k$$$. For each such run, the DC expression should not divide by $$$0$$$ at any time, and its value must be the number of derangements of $$$n$$$.

Examples
Input
2
Output
n-n/n
Input
3
Output
n+round(n-n*(n/(n+n)))-n
Note

For the first example, n-n/n is a valid DC program that calculates $$$n-1$$$. The number of derangements for $$$n=2$$$ is $$$1$$$, so this program correctly computes the answer for $$$n=2$$$.

In the second example, a slightly overcomplicated expression is used, which shows all the features of the language in action. For $$$n=3$$$, the value of the expression is: $$$3+\text{round}(3-3 \cdot(\frac{3}{3+3}))-3 = \text{round}(3 - \frac{3}{2}) = \text{round}(\frac{3}{2}) = \text{round}(1.5)=2$$$. It correctly calculates the number of derangements of the sequence $$$[1,2,3]$$$. For $$$n=2$$$ it can be verified that the value of the expression becomes $$$1$$$.