apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
YouKn0wWho has an integer sequence $$$a_1, a_2, \ldots a_n$$$. Now he will split the sequence $$$a$$$ into one or more consecutive subarrays so that each element of $$$a$$$ belongs to exactly one subarray. Let $$$k$$$ be the number of resulting subarrays, and $$$h_1, h_2, \ldots, h_k$$$ be the lengths of the longest increasing subsequences of corresponding subarrays.

For example, if we split $$$[2, 5, 3, 1, 4, 3, 2, 2, 5, 1]$$$ into $$$[2, 5, 3, 1, 4]$$$, $$$[3, 2, 2, 5]$$$, $$$[1]$$$, then $$$h = [3, 2, 1]$$$.

YouKn0wWho wonders if it is possible to split the sequence $$$a$$$ in such a way that the bitwise XOR of $$$h_1, h_2, \ldots, h_k$$$ is equal to $$$0$$$. You have to tell whether it is possible.

The longest increasing subsequence (LIS) of a sequence $$$b_1, b_2, \ldots, b_m$$$ is the longest sequence of valid indices $$$i_1, i_2, \ldots, i_k$$$ such that $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$ and $$$b_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}$$$. For example, the LIS of $$$[2, 5, 3, 3, 5]$$$ is $$$[2, 3, 5]$$$, which has length $$$3$$$.

An array $$$c$$$ is a subarray of an array $$$b$$$ if $$$c$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case, print "YES" (without quotes) if it is possible to split into subarrays in the desired way, print "NO" (without quotes) otherwise. You can print each letter in any register (upper or lower).

## Examples
```input
4
7
1 3 4 2 2 1 5
3
1 3 4
5
1 3 2 4 2
4
4 3 2 1
```
```output
YES
NO
YES
YES
```

## Note
In the first test case, YouKn0wWho can split the sequence in the following way: $$$[1, 3, 4]$$$, $$$[2, 2]$$$, $$$[1, 5]$$$. This way, the LIS lengths are $$$h = [3, 1, 2]$$$, and the bitwise XOR of the LIS lengths is $$$3 \oplus 1 \oplus 2 = 0$$$.

In the second test case, it can be shown that it is impossible to split the sequence into subarrays that will satisfy the condition.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A string is called square if it is some string written twice in a row. For example, the strings "aa", "abcabc", "abab" and "baabaa" are square. But the strings "aaa", "abaaab" and "abcdabc" are not square.

For a given string $$$s$$$ determine if it is square.

## Input Format
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) —the number of test cases.

This is followed by $$$t$$$ lines, each containing a description of one test case. The given strings consist only of lowercase Latin letters and have lengths between $$$1$$$ and $$$100$$$ inclusive.

## Output Format
For each test case, output on a separate line:

- YES if the string in the corresponding test case is square,
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

## Examples
```input
10
a
aa
aaa
aaaa
abab
abcabc
abacaba
xxyy
xyyx
xyxy
```
```output
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Tanya is learning how to add numbers, but so far she is not doing it correctly. She is adding two numbers $$$a$$$ and $$$b$$$ using the following algorithm:

1. If one of the numbers is shorter than the other, Tanya adds leading zeros so that the numbers are the same length.
2. The numbers are processed from right to left (that is, from the least significant digits to the most significant).
3. In the first step, she adds the last digit of $$$a$$$ to the last digit of $$$b$$$ and writes their sum in the answer.
4. At each next step, she performs the same operation on each pair of digits in the same place and writes the result to the left side of the answer.

For example, the numbers $$$a = 17236$$$ and $$$b = 3465$$$ Tanya adds up as follows:

$$$$$$ \large{ \begin{array}{r} + \begin{array}{r} 17236\\ 03465\\ \end{array} \\ \hline \begin{array}{r} 1106911 \end{array} \end{array}} $$$$$$

- calculates the sum of $$$6 + 5 = 11$$$ and writes $$$11$$$ in the answer.
- calculates the sum of $$$3 + 6 = 9$$$ and writes the result to the left side of the answer to get $$$911$$$.
- calculates the sum of $$$2 + 4 = 6$$$ and writes the result to the left side of the answer to get $$$6911$$$.
- calculates the sum of $$$7 + 3 = 10$$$, and writes the result to the left side of the answer to get $$$106911$$$.
- calculates the sum of $$$1 + 0 = 1$$$ and writes the result to the left side of the answer and get $$$1106911$$$.

As a result, she gets $$$1106911$$$.

You are given two positive integers $$$a$$$ and $$$s$$$. Find the number $$$b$$$ such that by adding $$$a$$$ and $$$b$$$ as described above, Tanya will get $$$s$$$. Or determine that no suitable $$$b$$$ exists.

## Input Format
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of a single line containing two positive integers $$$a$$$ and $$$s$$$ ($$$1 \le a \lt s \le 10^{18}$$$) separated by a space.

## Output Format
For each test case print the answer on a separate line.

If the solution exists, print a single positive integer $$$b$$$. The answer must be written without leading zeros. If multiple answers exist, print any of them.

If no suitable number $$$b$$$ exists, output -1.

## Examples
```input
6
17236 1106911
1 5
108 112
12345 1023412
1 11
1 20
```
```output
3465
4
-1
90007
10
-1
```

## Note
The first test case is explained in the main part of the statement.

In the third test case, we cannot choose $$$b$$$ that satisfies the problem statement.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Dmitry has an array of $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$.

In one operation, Dmitry can choose any index $$$j$$$ ($$$1 \le j \le n$$$) and increase the value of the element $$$a_j$$$ by $$$1$$$. He can choose the same index $$$j$$$ multiple times.

For each $$$i$$$ from $$$0$$$ to $$$n$$$, determine whether Dmitry can make the $$$\mathrm{MEX}$$$ of the array equal to exactly $$$i$$$. If it is possible, then determine the minimum number of operations to do it.

The $$$\mathrm{MEX}$$$ of the array is equal to the minimum non-negative integer that is not in the array. For example, the $$$\mathrm{MEX}$$$ of the array $$$[3, 1, 0]$$$ is equal to $$$2$$$, and the array $$$[3, 3, 1, 4]$$$ is equal to $$$0$$$.

## Input Format
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input.

The descriptions of the test cases follow.

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

The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — elements of the array $$$a$$$.

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

## Output Format
For each test case, output $$$n + 1$$$ integer — $$$i$$$-th number is equal to the minimum number of operations for which you can make the array $$$\mathrm{MEX}$$$ equal to $$$i$$$ ($$$0 \le i \le n$$$), or -1 if this cannot be done.

## Examples
```input
5
3
0 1 3
7
0 1 2 3 4 3 2
4
3 0 0 0
7
4 6 2 3 5 0 5
5
4 0 1 0 4
```
```output
1 1 0 -1 
1 1 2 2 1 0 2 6 
3 0 1 4 3 
1 0 -1 -1 -1 -1 -1 -1 
2 1 0 2 -1 -1
```

## Note
In the first set of example inputs, $$$n=3$$$:

- to get $$$\mathrm{MEX}=0$$$, it is enough to perform one increment: $$$a_1$$$++;
- to get $$$\mathrm{MEX}=1$$$, it is enough to perform one increment: $$$a_2$$$++;
- $$$\mathrm{MEX}=2$$$ for a given array, so there is no need to perform increments;
- it is impossible to get $$$\mathrm{MEX}=3$$$ by performing increments.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of size $$$n$$$.

You can perform the following operation on the array:

- Choose two different integers $$$i, j$$$ $$$(1 \leq i < j \leq n$$$), replace $$$a_i$$$ with $$$x$$$ and $$$a_j$$$ with $$$y$$$. In order not to break the array, $$$a_i | a_j = x | y$$$ must be held, where $$$|$$$ denotes the bitwise OR operation. Notice that $$$x$$$ and $$$y$$$ are non-negative integers.

Please output the minimum sum of the array you can get after using the operation above any number of times.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 1000)$$$. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ $$$(2 \leq n \leq 100)$$$ — the size of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(0 \leq a_i < 2^{30})$$$.

## Output Format
For each test case, print one number in a line — the minimum possible sum of the array.

## Examples
```input
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
```
```output
3
31
6
7
```

## Note
In the first example, you can perform the following operations to obtain the array $$$[1, 0, 2]$$$:

1. choose $$$i = 1, j = 2$$$, change $$$a_1 = 1$$$ and $$$a_2 = 2$$$, it's valid since $$$1 | 3 = 1 | 2$$$. The array becomes $$$[1, 2, 2]$$$.

2. choose $$$i = 2, j = 3$$$, change $$$a_2 = 0$$$ and $$$a_3 = 2$$$, it's valid since $$$2 | 2 = 0 | 2$$$. The array becomes $$$[1, 0, 2]$$$.

We can prove that the minimum sum is $$$1 + 0 + 2 = 3$$$

In the second example, We don't need any operations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of size $$$n$$$. Each element in this array is an integer between $$$1$$$ and $$$10^9$$$.

You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between $$$1$$$ and $$$10^9$$$.

Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.

An element $$$a_i$$$ is a local maximum if it is strictly larger than both of its neighbors (that is, $$$a_i > a_{i - 1}$$$ and $$$a_i > a_{i + 1}$$$). Since $$$a_1$$$ and $$$a_n$$$ have only one neighbor each, they will never be a local maximum.

## Input Format
Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, the elements of array.

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, first output a line containing a single integer $$$m$$$ — minimum number of operations required. Then ouput a line consist of $$$n$$$ integers — the resulting array after the operations. Note that this array should differ in exactly $$$m$$$ elements from the initial array.

If there are multiple answers, print any.

## Examples
```input
5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3
```
```output
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3
```

## Note
In the first example, the array contains no local maximum, so we don't need to perform operations.

In the second example, we can change $$$a_2$$$ to $$$3$$$, then the array don't have local maximums.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ elements.

Your can perform the following operation no more than $$$n$$$ times: Select three indices $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$ and replace $$$a_x$$$ with $$$a_y - a_z$$$. After the operation, $$$|a_x|$$$ need to be less than $$$10^{18}$$$.

Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.

## Input Format
Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$, the elements of $$$a$$$.

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, print $$$-1$$$ in a single line if there is no solution. Otherwise in the first line you should print a single integer $$$m$$$ $$$(0 \leq m \leq n)$$$ — number of operations you performed.

Then the $$$i$$$-th of the following $$$m$$$ lines should contain three integers $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$— description of the $$$i$$$-th operation.

If there are multiple solutions, you can output any. Note that you don't have to minimize the number of operations in this task.

## Examples
```input
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
```
```output
2
1 2 3
3 4 5
-1
0
```

## Note
In the first example, the array becomes

$$$[-6,-4,2,-1,2]$$$ after the first operation,

$$$[-6,-4,-3,-1,2]$$$ after the second operation.

In the second example, it is impossible to make the array sorted after any sequence of operations.

In the third example, the array is already sorted, so we don't need to perform any operations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ distinct positive integers.

Let's consider an infinite integer set $$$S$$$ which contains all integers $$$x$$$ that satisfy at least one of the following conditions:

1. $$$x = a_i$$$ for some $$$1 \leq i \leq n$$$.
2. $$$x = 2y + 1$$$ and $$$y$$$ is in $$$S$$$.
3. $$$x = 4y$$$ and $$$y$$$ is in $$$S$$$.

For example, if $$$a = [1,2]$$$ then the $$$10$$$ smallest elements in $$$S$$$ will be $$$\{1,2,3,4,5,7,8,9,11,12\}$$$.

Find the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$p$$$ $$$(1 \leq n, p \leq 2 \cdot 10^5)$$$.

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

It is guaranteed that all the numbers in $$$a$$$ are distinct.

## Output Format
Print a single integer, the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Remember to print it modulo $$$10^9 + 7$$$.

## Examples
```input
2 4
6 1
```
```output
9
```
-----
```input
4 7
20 39 5 200
```
```output
14
```
-----
```input
2 200000
48763 1000000000
```
```output
448201910
```

## Note
In the first example, the elements smaller than $$$2^4$$$ are $$$\{1, 3, 4, 6, 7, 9, 12, 13, 15\}$$$.

In the second example, the elements smaller than $$$2^7$$$ are $$$\{5,11,20,23,39,41,44,47,79,80,83,89,92,95\}$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There's a chip in the point $$$(0, 0)$$$ of the coordinate plane. In one operation, you can move the chip from some point $$$(x_1, y_1)$$$ to some point $$$(x_2, y_2)$$$ if the Euclidean distance between these two points is an integer (i.e. $$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$$ is integer).

Your task is to determine the minimum number of operations required to move the chip from the point $$$(0, 0)$$$ to the point $$$(x, y)$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3000$$$) — number of test cases.

The single line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 50$$$) — the coordinates of the destination point.

## Output Format
For each test case, print one integer — the minimum number of operations required to move the chip from the point $$$(0, 0)$$$ to the point $$$(x, y)$$$.

## Examples
```input
3
8 6
0 0
9 15
```
```output
1
0
2
```

## Note
In the first example, one operation $$$(0, 0) \rightarrow (8, 6)$$$ is enough. $$$\sqrt{(0-8)^2+(0-6)^2}=\sqrt{64+36}=\sqrt{100}=10$$$ is an integer.

In the second example, the chip is already at the destination point.

In the third example, the chip can be moved as follows: $$$(0, 0) \rightarrow (5, 12) \rightarrow (9, 15)$$$. $$$\sqrt{(0-5)^2+(0-12)^2}=\sqrt{25+144}=\sqrt{169}=13$$$ and $$$\sqrt{(5-9)^2+(12-15)^2}=\sqrt{16+9}=\sqrt{25}=5$$$ are integers.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given four integers $$$n$$$, $$$B$$$, $$$x$$$ and $$$y$$$. You should build a sequence $$$a_0, a_1, a_2, \dots, a_n$$$ where $$$a_0 = 0$$$ and for each $$$i \ge 1$$$ you can choose:

- either $$$a_i = a_{i - 1} + x$$$
- or $$$a_i = a_{i - 1} - y$$$.

Your goal is to build such a sequence $$$a$$$ that $$$a_i \le B$$$ for all $$$i$$$ and $$$\sum\limits_{i=0}^{n}{a_i}$$$ is maximum possible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Next $$$t$$$ cases follow.

The first and only line of each test case contains four integers $$$n$$$, $$$B$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le B, x, y \le 10^9$$$).

It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the maximum possible $$$\sum\limits_{i=0}^{n}{a_i}$$$.

## Examples
```input
3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3
```
```output
15
4000000000
-10
```

## Note
In the first test case, the optimal sequence $$$a$$$ is $$$[0, 1, 2, 3, 4, 5]$$$.

In the second test case, the optimal sequence $$$a$$$ is $$$[0, 10^9, 0, 10^9, 0, 10^9, 0, 10^9]$$$.

In the third test case, the optimal sequence $$$a$$$ is $$$[0, -3, -6, 1, -2]$$$.

Now solve the problem and return the code.