Codeforces Round 873 (Div. 2)
A. Divisible Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Please find an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

A perfect array $$$a_1, a_2, \ldots, a_n$$$ satisfies the following criteria:

  • $$$1 \le a_i \le 1000$$$ for all $$$1 \le i \le n$$$.
  • $$$a_i$$$ is divisible by $$$i$$$ for all $$$1 \le i \le n$$$.
  • $$$a_1 + a_2 + \ldots + a_n$$$ is divisible by $$$n$$$.
Input

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

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

Output

For each test case, output an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

We can show that an answer always exists. If there are multiple solutions, print any.

Example
Input
7
1
2
3
4
5
6
7
Output
1
2 4
1 2 3
2 8 6 4
3 4 9 4 5
1 10 18 8 5 36
3 6 21 24 10 6 14
Note

In the third test case:

  • $$$a_1 = 1$$$ is divisible by $$$1$$$.
  • $$$a_2 = 2$$$ is divisible by $$$2$$$.
  • $$$a_3 = 3$$$ is divisible by $$$3$$$.
  • $$$a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$$$ is divisible by $$$3$$$.

In the fifth test case:

  • $$$a_1 = 3$$$ is divisible by $$$1$$$.
  • $$$a_2 = 4$$$ is divisible by $$$2$$$.
  • $$$a_3 = 9$$$ is divisible by $$$3$$$.
  • $$$a_4 = 4$$$ is divisible by $$$4$$$.
  • $$$a_5 = 5$$$ is divisible by $$$5$$$.
  • $$$a_1 + a_2 + a_3 + a_4 + a_5 = 3 + 4 + 9 + 4 + 5 = 25$$$ is divisible by $$$5$$$.

B. Permutation Swap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an unsorted permutation $$$p_1, p_2, \ldots, p_n$$$. To sort the permutation, you choose a constant $$$k$$$ ($$$k \ge 1$$$) and do some operations on the permutation. In one operation, you can choose two integers $$$i$$$, $$$j$$$ ($$$1 \le j \lt i \le n$$$) such that $$$i - j = k$$$, then swap $$$p_i$$$ and $$$p_j$$$.

What is the maximum value of $$$k$$$ that you can choose to sort the given permutation?

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

An unsorted permutation $$$p$$$ is a permutation such that there is at least one position $$$i$$$ that satisfies $$$p_i \ne i$$$.

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$$$ ($$$2 \le n \le 10^{5}$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$. It is guaranteed that the given numbers form a permutation of length $$$n$$$ and the given permutation is unsorted.

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 the maximum value of $$$k$$$ that you can choose to sort the given permutation.

We can show that an answer always exists.

Example
Input
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2
Output
1
2
3
4
3
2
3
Note

In the first test case, the maximum value of $$$k$$$ you can choose is $$$1$$$. The operations used to sort the permutation are:

  • Swap $$$p_2$$$ and $$$p_1$$$ ($$$2 - 1 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 3, 2]$$$
  • Swap $$$p_2$$$ and $$$p_3$$$ ($$$3 - 2 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3]$$$

In the second test case, the maximum value of $$$k$$$ you can choose is $$$2$$$. The operations used to sort the permutation are:

  • Swap $$$p_3$$$ and $$$p_1$$$ ($$$3 - 1 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 4, 3, 2]$$$
  • Swap $$$p_4$$$ and $$$p_2$$$ ($$$4 - 2 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3, 4]$$$

C. Counting Orders
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ each consisting of $$$n$$$ integers. All elements of $$$a$$$ are pairwise distinct.

Find the number of ways to reorder $$$a$$$ such that $$$a_i \gt b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.

Two ways of reordering are considered different if the resulting arrays are different.

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 length of the array $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$. It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

The second line of each test case contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the array $$$b$$$.

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 the number of ways to reorder array $$$a$$$ such that $$$a_i \gt b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.

Example
Input
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
Output
32
0
1
0
13824

D1. Range Sorting (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between this problem and the hard version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$.

Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:

  • Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le k$$$).
  • Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds.

Please calculate the sum of beauty over all subarrays of array $$$a$$$.

A subarray of an array is defined as a sequence of consecutive elements of the array.

Input

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

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

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

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

Output

For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Example
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
Note

In the first test case:

  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.

In the second test case:

  • The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.
  • You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

D2. Range Sorting (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between this problem and the easy version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$.

Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:

  • Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le k$$$).
  • Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds.

Please calculate the sum of beauty over all subarrays of array $$$a$$$.

A subarray of an array is defined as a sequence of consecutive elements of the array.

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 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.

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

Output

For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Example
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
Note

In the first test case:

  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.

In the second test case:

  • The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.
  • The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.
  • You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.
  • You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.
The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

E. Palindrome Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A substring is a continuous and non-empty segment of letters from a given string, without any reorders.

An even palindrome is a string that reads the same backward as forward and has an even length. For example, strings "zz", "abba", "abccba" are even palindromes, but strings "codeforces", "reality", "aba", "c" are not.

A beautiful string is an even palindrome or a string that can be partitioned into some smaller even palindromes.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. Count the number of beautiful substrings of $$$s$$$.

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 5\cdot 10^5$$$).

The second line of each test case contains a string $$$s$$$. String $$$s$$$ consists of only lowercase Latin letters and has a length of $$$n$$$.

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

Output

For each test case print the number of beautiful substrings.

Example
Input
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Output
3
0
1
0
14
6
Note

In the first test case, the beautiful substrings are "abaaba", "baab", "aa".

In the last test case, the beautiful substrings are "aa" (counted twice), "abba", "bb", "bbaa", "abbaaa".

F. Two Centroids
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree (an undirected connected acyclic graph) which initially only contains vertex $$$1$$$. There will be several queries to the given tree. In the $$$i$$$-th query, vertex $$$i + 1$$$ will appear and be connected to vertex $$$p_i$$$ ($$$1 \le p_i \le i$$$).

After each query, please find out the least number of operations required to make the current tree has two centroids. In one operation, you can add one vertex and one edge to the tree such that it remains a tree.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $$$\lfloor \frac{n}{2} \rfloor$$$ vertices each, with $$$n$$$ as the number of vertices of the tree. For example, the centroid of the following tree is $$$3$$$ because the biggest subtree after removing the centroid has $$$2$$$ vertices.

In the next tree, vertex $$$1$$$ and $$$2$$$ are both centroids.

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$$$ ($$$2 \le n \le 5 \cdot 10^{5}$$$) — the number of nodes of the final tree.

The second line of each test case contains $$$n - 1$$$ integers $$$p_1, p_2, \ldots, p_{n - 1}$$$ ($$$1 \le p_i \le i$$$) — the index of the vertex that is connected to vertex $$$i + 1$$$.

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

Output

For each test case, output $$$n - 1$$$ integers. The $$$i$$$-th integer is the answer to the $$$i$$$-th query — the least number of operations required to make the current tree have two centroids.

We can show that an answer always exists.

Example
Input
5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9
Output
0
0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2
Note

The illustrations below are of the fourth example test case.

After the third query:

The tree already has vertices $$$2$$$ and $$$3$$$ as centroids, so no operations are needed.

After the fourth query:

Adding vertex $$$x$$$ to the tree makes vertices $$$2$$$ and $$$3$$$ centroids. Only one operation is needed.

After the fifth query:

Adding vertex $$$x$$$ and $$$y$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Two operations are needed.

After the sixth query:

Adding vertex $$$x$$$, $$$y$$$, and $$$z$$$ to the tree makes vertices $$$5$$$ and $$$2$$$ centroids. Three operations are needed.