1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimal Coprime
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 800
Tags: math, number theory

Today, Little John used all his savings to buy a segment. He wants to build a house on this segment.

A segment of positive integers $$$[l,r]$$$ is called coprime if $$$l$$$ and $$$r$$$ are coprime$$$^{\text{∗}}$$$.

A coprime segment $$$[l,r]$$$ is called minimal coprime if it does not contain$$$^{\text{†}}$$$ any coprime segment not equal to itself. To better understand this statement, you can refer to the notes.

Given $$$[l,r]$$$, a segment of positive integers, find the number of minimal coprime segments contained in $$$[l,r]$$$.

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

The only line of each test case consists of two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^9$$$).

Output format:
For each test case, output the number of minimal coprime segments contained in $$$[l,r]$$$, on a separate line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
On the first test case, the given segment is $$$[1,2]$$$. The segments contained in $$$[1,2]$$$ are as follows.

- $$$[1,1]$$$: This segment is coprime, since the numbers $$$1$$$ and $$$1$$$ are coprime, and this segment does not contain any other segment inside. Thus, $$$[1,1]$$$ is minimal coprime.
- $$$[1,2]$$$: This segment is coprime. However, as it contains $$$[1,1]$$$, which is also coprime, $$$[1,2]$$$ is not minimal coprime.
- $$$[2,2]$$$: This segment is not coprime because $$$2$$$ and $$$2$$$ share $$$2$$$ positive common divisors: $$$1$$$ and $$$2$$$.

Therefore, the segment $$$[1,2]$$$ contains $$$1$$$ minimal coprime segment.

Example input:
6
1 2
1 10
49 49
69 420
1 1
9982 44353

Example output:
1
9
0
351
1
34371

Editorial:
It is easy to see that two integers $$$l$$$ and $$$l+1$$$ are always coprime, due to $$$\gcd(l,l+1)=\gcd(1,l)=\gcd(0,1)=1$$$. Thus, all segments in the form $$$[l,l+1]$$$ are coprime, and all minimal coprime segments must have a size of at most $$$2$$$ (otherwise, it will contain another segment of size $$$2$$$).
It can be observed that the only coprime segment with size $$$1$$$ is $$$[1,1]$$$ as $$$\gcd(a,a)=a$$$. The set of minimal coprime segments is as follows:
• $$$[1,1]$$$ is minimal coprime.
• For all $$$l>1$$$, $$$[l,l+1]$$$ is minimal coprime.
And there is no other segment that is minimal coprime.
The solution is thus as follows:
• If $$$x=y=1$$$, it contains $$$[1,1]$$$ and the answer is $$$1$$$.
• Otherwise, $$$y>1$$$. There exists exactly one $$$l$$$ for all $$$x \le l < y$$$ such that $$$[l,*]$$$ is minimal coprime and is contained in $$$[x,y]$$$.   In other words, the answer is $$$(y-1)-x+1=y-x$$$ in this case.
• In other words, the answer is $$$(y-1)-x+1=y-x$$$ in this case.
The problem has been solved with time complexity $$$\mathcal{O}(1)$$$ per test case.
Alice's Adventures in "Chess"
Contest: Codeforces Round 986 (Div. 2)
Difficulty rating: 900
Tags: brute force, implementation, math

Alice is trying to meet up with the Red Queen in the countryside! Right now, Alice is at position $$$(0, 0)$$$, and the Red Queen is at position $$$(a, b)$$$. Alice can only move in the four cardinal directions (north, east, south, west).

More formally, if Alice is at the point $$$(x, y)$$$, she will do one of the following:

- go north (represented by N), moving to $$$(x, y+1)$$$;
- go east (represented by E), moving to $$$(x+1, y)$$$;
- go south (represented by S), moving to $$$(x, y-1)$$$; or
- go west (represented by W), moving to $$$(x-1, y)$$$.

Alice's movements are predetermined. She has a string $$$s$$$ representing a sequence of moves that she performs from left to right. Once she reaches the end of the sequence, she repeats the same pattern of moves forever.

Can you help Alice figure out if she will ever meet the Red Queen?

Input format:
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 three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \le n$$$, $$$a$$$, $$$b \le 10$$$) — the length of the string and the initial coordinates of the Red Queen.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting only of the characters N, E, S, or W.

Output format:
For each test case, output a single string "YES" or "NO" (without the quotes) denoting whether Alice will eventually meet the Red Queen.

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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Alice follows the path $$$(0,0) \xrightarrow[\texttt{N}]{} (0,1) \xrightarrow[\texttt{E}]{} (1,1) \xrightarrow[\texttt{N}]{} (1,2) \xrightarrow[\texttt{E}]{} (2,2)$$$.

In the second test case, Alice can never reach the Red Queen.

Example input:
6
2 2 2
NE
3 2 2
NNE
6 2 1
NNEESW
6 10 10
NNEESW
3 4 2
NEE
4 5 5
NEWS

Example output:
YES
NO
YES
YES
YES
NO

Editorial:
We can run the whole pattern $$$100\gg \max(a, b, n)$$$ times, which gives a total runtime of $$$O(100tn)$$$ (be careful in that running the pattern only 10 times is not enough!)
To prove that $$$100$$$ repeats suffices, suppose that Alice's steps on the first run of the pattern are $$$(0, 0), (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ (we will take $$$x_0 = 0, y_0 = 0$$$ for convenience) Then, Alice ends up at position $$$(a, b)$$$ if there exists a $$$t\ge 0$$$ (the number of extra repeats) such that for some $$$i$$$, $$$x_i + tx_n = a$$$ and $$$y_i + ty_n = b$$$.
Certainly, if $$$x_n = y_n = 0$$$, we only need one repeat so assume WLOG that $$$x_n \neq 0$$$. Then, it must be the case that $$$t = \frac{a - x_i}{x_n}$$$. However, $$$a - x_i \le 20$$$ (since $$$x_i \ge -10$$$) and $$$|x_n|\ge 1$$$, so $$$t \le 20$$$ and therefore $$$21$$$ repeats always suffice.
In fact, the above proof shows that we can solve each testcase in time $$$O(n)$$$.
Max Plus Size
Contest: Codeforces Round 975 (Div. 2)
Difficulty rating: 800
Tags: brute force, dp, greedy

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

You can color some elements of the array red, but there cannot be two adjacent red elements (i.e., for $$$1 \leq i \leq n-1$$$, at least one of $$$a_i$$$ and $$$a_{i+1}$$$ must not be red).

Your score is the maximum value of a red element plus the number of red elements. Find the maximum score you can get.

Input format:
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 length of the array.

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

Output format:
For each test case, output a single integer: the maximum possible score you can get after coloring some elements red according to the statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can color the array as follows: $$$[\color{red}{5}, 4, \color{red}{5}]$$$. Your score is $$$\max([5, 5]) + \text{size}([5, 5]) = 5+2 = 7$$$. This is the maximum score you can get.

In the second test case, you can color the array as follows: $$$[\color{red}{4}, 5, \color{red}{4}]$$$. Your score is $$$\max([4, 4]) + \text{size}([4, 4]) = 4+2 = 6$$$. This is the maximum score you can get.

In the third test case, you can color the array as follows: $$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 4, \color{red}{5}]$$$. Your score is $$$\max([3, 3, 4, 3, 5]) + \text{size}([3, 3, 4, 3, 5]) = 5+5 = 10$$$. This is the maximum score you can get.

Example input:
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 4 5
9
17 89 92 42 29 92 14 70 45

Example output:
7
6
10
97

Editorial:
All Pairs Segments
Contest: Codeforces Round 975 (Div. 2)
Difficulty rating: 1200
Tags: implementation, math

You are given $$$n$$$ points on the $$$x$$$ axis, at increasing positive integer coordinates $$$x_1 < x_2 < \ldots < x_n$$$.

For each pair $$$(i, j)$$$ with $$$1 \leq i < j \leq n$$$, you draw the segment $$$[x_i, x_j]$$$. The segments are closed, i.e., a segment $$$[a, b]$$$ contains the points $$$a, a+1, \ldots, b$$$.

You are given $$$q$$$ queries. In the $$$i$$$-th query, you are given a positive integer $$$k_i$$$, and you have to determine how many points with integer coordinates are contained in exactly $$$k_i$$$ segments.

Input format:
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$$$, $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of points and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$$$) — the coordinates of the $$$n$$$ points.

The third line of each test case contains $$$q$$$ integers $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq 10^{18}$$$) — the parameters of the $$$q$$$ queries.

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

Output format:
For each test case, output a single line with $$$q$$$ integers: the $$$i$$$-th integer is the answer to the $$$i$$$-th query.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example, you only draw the segment $$$[101, 200]$$$. No point is contained in exactly $$$2$$$ segments, and the $$$100$$$ points $$$101, 102, \ldots, 200$$$ are contained in exactly $$$1$$$ segment.

In the second example, you draw $$$15$$$ segments: $$$[1, 2], [1, 3], [1, 5], [1, 6], [1, 7], [2, 3], [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [5, 6], [5, 7], [6, 7]$$$. Points $$$1, 7$$$ are contained in exactly $$$5$$$ segments; points $$$2, 4, 6$$$ are contained in exactly $$$9$$$ segments; points $$$3, 5$$$ are contained in exactly $$$11$$$ segments.

Example input:
3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300

Example output:
0 100 
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0 
291716045 0 0 0 291716045 0 301749698 0

Editorial:
Find K Distinct Points with Fixed Center
Contest: Codeforces Round 965 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation, math

You are given three integers $$$x_c$$$, $$$y_c$$$, and $$$k$$$ ($$$-100 \leq x_c, y_c \leq 100$$$, $$$1 \leq k \leq 1000$$$).

You need to find $$$k$$$ distinct points ($$$x_1, y_1$$$), ($$$x_2, y_2$$$), $$$\ldots$$$, ($$$x_k, y_k$$$), having integer coordinates, on the 2D coordinate plane such that:

- their center$$$^{\text{∗}}$$$ is ($$$x_c, y_c$$$)
- $$$-10^9 \leq x_i, y_i \leq 10^9$$$ for all $$$i$$$ from $$$1$$$ to $$$k$$$

It can be proven that at least one set of $$$k$$$ distinct points always exists that satisfies these conditions.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Each test case contains three integers $$$x_c$$$, $$$y_c$$$, and $$$k$$$ ($$$-100 \leq x_c, y_c \leq 100$$$, $$$1 \leq k \leq 1000$$$) — the coordinates of the center and the number of distinct points you must output.

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

Output format:
For each test case, output $$$k$$$ lines, the $$$i$$$-th line containing two space separated integers, $$$x_i$$$ and $$$y_i$$$, ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — denoting the position of the $$$i$$$-th point.

If there are multiple answers, print any of them. It can be shown that a solution always exists under the given constraints.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, $$$\left( \frac{10}{1}, \frac{10}{1} \right) = (10, 10)$$$.

For the second test case, $$$\left( \frac{-1 + 5 - 4}{3}, \frac{-1 -1 + 2}{3} \right) = (0, 0)$$$.

Example input:
4
10 10 1
0 0 3
-5 -8 8
4 -5 3

Example output:
10 10
-1 -1
5 -1
-4 2
-6 -7
-5 -7
-4 -7
-4 -8
-4 -9
-5 -9
-6 -9
-6 -8
1000 -1000
-996 995
8 -10

Editorial:
Minimize Equal Sum Subarrays
Contest: Codeforces Round 965 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, math, number theory

You are given a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$.

Find a permutation $$$q$$$ of length $$$n$$$ that minimizes the number of pairs ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) such that $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The following line contains $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — denoting the permutation $$$p$$$ of length $$$n$$$.

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

Output format:
For each test case, output one line containing any permutation of length $$$n$$$ (the permutation $$$q$$$) such that $$$q$$$ minimizes the number of pairs.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
For the first test, there exists only one pair ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) such that $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$, which is ($$$1, 2$$$). It can be proven that no such $$$q$$$ exists for which there are no pairs.

Example input:
3
2
1 2
5
1 2 3 4 5
7
4 7 5 1 2 6 3

Example output:
2 1
3 5 4 2 1
6 2 1 4 7 3 5

Editorial:
Perform Operations to Maximize Score
Contest: Codeforces Round 965 (Div. 2)
Difficulty rating: 1900
Tags: binary search, brute force, constructive algorithms, greedy, implementation

You are given an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$. You are also given a binary array $$$b$$$ of length $$$n$$$.

You can perform the following operation at most $$$k$$$ times:

- Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that $$$b_i = 1$$$. Set $$$a_i = a_i + 1$$$ (i.e., increase $$$a_i$$$ by $$$1$$$).

Your score is defined to be $$$\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$$$, where $$$c_i$$$ denotes the array of length $$$n-1$$$ that you get by deleting $$$a_i$$$ from $$$a$$$. In other words, your score is the maximum value of $$$a_i + \operatorname{median}(c_i)$$$ over all $$$i$$$ from $$$1$$$ to $$$n$$$.

Find the maximum score that you can achieve if you perform the operations optimally.

For an arbitrary array $$$p$$$, $$$\operatorname{median}(p)$$$ is defined as the $$$\left\lfloor \frac{|p|+1}{2} \right\rfloor$$$-th smallest element of $$$p$$$. For example, $$$\operatorname{median} \left( [3,2,1,3] \right) = 2$$$ and $$$\operatorname{median} \left( [6,2,4,5,1] \right) = 4$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

Each test case begins with two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$) — the length of the $$$a$$$ and the number of operations you can perform.

The following line contains $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — denoting the array $$$a$$$.

The following line contains $$$n$$$ space separated integers $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i$$$ is $$$0$$$ or $$$1$$$) — denoting the array $$$b$$$.

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

Output format:
For each test case, output the maximum value of score you can get on a new line.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first test case, it is optimal to perform $$$5$$$ operations on both elements so $$$a = [8,8]$$$. So, the maximum score we can achieve is $$$\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16$$$, as $$$c_1 = [a_2] = [8]$$$. It can be proven that you cannot get a better score.

For the second test case, you are not able to perform operations on any elements, so $$$a$$$ remains $$$[3,3,3]$$$. So, the maximum score we can achieve is $$$3 + \operatorname{median}[3, 3] = 6$$$, as $$$c_1 = [a_2, a_3] = [3, 3]$$$. It can be proven that you cannot get a better score.

Example input:
8
2 10
3 3
1 1
3 10
3 3 3
0 0 0
4 4
2 1 5 1
0 1 0 1
5 4
7 5 2 5 4
0 0 1 0 1
5 1
5 15 15 2 11
1 0 0 1 1
5 2
10 11 4 10 15
1 1 0 1 0
4 4
1 1 2 5
1 1 0 0
2 1000000000
1000000000 1000000000
1 1

Example output:
16
6
8
13
21
26
8
3000000000

Editorial:
Eliminating Balls With Merging (Hard Version)
Contest: Codeforces Round 965 (Div. 2)
Difficulty rating: 2500
Tags: binary search, brute force, data structures, divide and conquer, greedy, implementation

This is the hard version of the problem. The only difference is that $$$x=1$$$ in this version. You must solve both versions to be able to hack.

You are given two integers $$$n$$$ and $$$x$$$ ($$$x=1$$$). There are $$$n$$$ balls lined up in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, there is a value $$$a_i$$$ written on the $$$i$$$-th ball.

For each integer $$$i$$$ from $$$1$$$ to $$$n$$$, we define a function $$$f(i)$$$ as follows:

- Suppose you have a set $$$S = \{1, 2, \ldots, i\}$$$.
- In each operation, you have to select an integer $$$l$$$ ($$$1 \leq l < i$$$) from $$$S$$$ such that $$$l$$$ is not the largest element of $$$S$$$. Suppose $$$r$$$ is the smallest element in $$$S$$$ which is greater than $$$l$$$.   If $$$a_l > a_r$$$, you set $$$a_l = a_l + a_r$$$ and remove $$$r$$$ from $$$S$$$.  If $$$a_l < a_r$$$, you set $$$a_r = a_l + a_r$$$ and remove $$$l$$$ from $$$S$$$.  If $$$a_l = a_r$$$, you choose either the integer $$$l$$$ or $$$r$$$ to remove from $$$S$$$:   If you choose to remove $$$l$$$ from $$$S$$$, you set $$$a_r = a_l + a_r$$$ and remove $$$l$$$ from $$$S$$$.  If you choose to remove $$$r$$$ from $$$S$$$, you set $$$a_l = a_l + a_r$$$ and remove $$$r$$$ from $$$S$$$.
- $$$f(i)$$$ denotes the number of integers $$$j$$$ ($$$1 \le j \le i$$$) such that it is possible to obtain $$$S = \{j\}$$$ after performing the above operations exactly $$$i - 1$$$ times.

For each integer $$$i$$$ from $$$x$$$ to $$$n$$$, you need to find $$$f(i)$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5; x = 1$$$) — the number of balls and the smallest index $$$i$$$ for which you need to find $$$f(i)$$$.

The second line of each test case contains $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial number written on each ball.

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

Output format:
For each test case, output $$$n-x+1$$$ space separated integers on a new line, where the $$$j$$$-th integer should represent $$$f(x+j-1)$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, below are the possible values of $$$j$$$ for each $$$f(i)$$$ from $$$1$$$ to $$$n$$$.

- For $$$f(1)$$$, the only possible value of $$$j$$$ is $$$1$$$.
- For $$$f(2)$$$, the only possible value of $$$j$$$ is $$$2$$$.
- For $$$f(3)$$$, the possible values of $$$j$$$ are $$$2$$$ and $$$3$$$.
- For $$$f(4)$$$, the possible values of $$$j$$$ are $$$2$$$ and $$$3$$$.
- For $$$f(5)$$$, the possible values of $$$j$$$ are $$$2$$$, $$$3$$$, and $$$4$$$.

Example input:
3
5 1
1 2 3 2 1
7 1
4 5 1 2 1 4 5
11 1
1 2 3 1 1 9 3 2 4 1 3

Example output:
1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4

Editorial:
A Gift From Orangutan
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, math, sortings

While exploring the jungle, you have bumped into a rare orangutan with a bow tie! You shake hands with the orangutan and offer him some food and water. In return...

The orangutan has gifted you an array $$$a$$$ of length $$$n$$$. Using $$$a$$$, you will construct two arrays $$$b$$$ and $$$c$$$, both containing $$$n$$$ elements, in the following manner:

- $$$b_i = \min(a_1, a_2, \ldots, a_i)$$$ for each $$$1 \leq i \leq n$$$.
- $$$c_i = \max(a_1, a_2, \ldots, a_i)$$$ for each $$$1 \leq i \leq n$$$.

Define the score of $$$a$$$ as $$$\sum_{i=1}^n c_i - b_i$$$ (i.e. the sum of $$$c_i - b_i$$$ over all $$$1 \leq i \leq n$$$). Before you calculate the score, you can shuffle the elements of $$$a$$$ however you want.

Find the maximum score that you can get if you shuffle the elements of $$$a$$$ optimally.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of elements in $$$a$$$.

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — the elements of the array $$$a$$$.

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

Output format:
For each test case, output the maximum score that you can get.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there is no other way to rearrange $$$a$$$. So, $$$b = [69]$$$ and $$$c = [69]$$$. The only possible score is $$$69 - 69 = 0$$$.

In the second test case, you can rearrange $$$a$$$ as $$$[7, 5, 6]$$$. Here, $$$b = [7, 5, 5]$$$ and $$$c = [7, 7, 7]$$$. The score in this case is $$$(7 - 7) + (7 - 5) + (7 - 5) = 4$$$. It can be shown this is the maximum possible score.

Example input:
3
1
69
3
7 6 5
5
1 1 1 2 2

Example output:
0
4
4

Editorial: