yl-9/probench huggingface dataset:
# Common Generator

## Problem Description

For two integers $ x $ and $ y $ ( $ x,y\ge 2 $ ), we will say that $ x $ is a generator of $ y $ if and only if $ x $ can be transformed to $ y $ by performing the following operation some number of times (possibly zero):

- Choose a divisor $ d $ ( $ d\ge 2 $ ) of $ x $ , then increase $ x $ by $ d $ .

For example,

- $ 3 $ is a generator of $ 8 $ since we can perform the following operations: $ 3 \xrightarrow{d = 3} 6 \xrightarrow{d = 2} 8 $ ;
- $ 4 $ is a generator of $ 10 $ since we can perform the following operations: $ 4 \xrightarrow{d = 4} 8 \xrightarrow{d = 2} 10 $ ;
- $ 5 $ is not a generator of $ 6 $ since we cannot transform $ 5 $ into $ 6 $ with the operation above.

Now, Kevin gives you an array $ a $ consisting of $ n $ pairwise distinct integers ( $ a_i\ge 2 $ ).

You have to find an integer $ x\ge 2 $ such that for each $ 1\le i\le n $ , $ x $ is a generator of $ a_i $ , or determine that such an integer does not exist.

## Input Format

Each test contains multiple test cases. The first line of the input 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 10^5 $ ) — the length of the array $ a $ .

The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 2\le a_i\le 4\cdot 10^5 $ ) — the elements in the array $ a $ . It is guaranteed that the elements are pairwise distinct.

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

## Output Format

For each test case, output a single integer $ x $ — the integer you found. Print $ -1 $ if there does not exist a valid $ x $ .

If there are multiple answers, you may output any of them.

## Sample #1

### Sample Input #1

```
4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000
```

### Sample Output #1

```
2
-1
7
3
```

## Hint

In the first test case, for $ x=2 $ :

- $ 2 $ is a generator of $ 8 $ , since we can perform the following operations: $ 2 \xrightarrow{d = 2} 4 \xrightarrow{d = 4} 8 $ ;
- $ 2 $ is a generator of $ 9 $ , since we can perform the following operations: $ 2 \xrightarrow{d = 2} 4 \xrightarrow{d = 2} 6 \xrightarrow{d = 3} 9 $ .
- $ 2 $ is a generator of $ 10 $ , since we can perform the following operations: $ 2 \xrightarrow{d = 2} 4 \xrightarrow{d = 2} 6 \xrightarrow{d = 2} 8 \xrightarrow{d = 2} 10 $ .

In the second test case, it can be proven that it is impossible to find a common generator of the four integers.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, constructive algorithms, math, number theory
Difficulty: 2100
# Replacement

## Problem Description

You have a binary string $ ^{\text{∗}} $ $ s $ of length $ n $ , and Iris gives you another binary string $ r $ of length $ n-1 $ .

Iris is going to play a game with you. During the game, you will perform $ n-1 $ operations on $ s $ . In the $ i $ -th operation ( $ 1 \le i \le n-1 $ ):

- First, you choose an index $ k $ such that $ 1\le k\le |s| - 1 $ and $ s_{k} \neq s_{k+1} $ . If it is impossible to choose such an index, you lose;
- Then, you replace $ s_ks_{k+1} $ with $ r_i $ . Note that this decreases the length of $ s $ by $ 1 $ .

If all the $ n-1 $ operations are performed successfully, you win.

Determine whether it is possible for you to win this game.

 $ ^{\text{∗}} $ A binary string is a string where each character is either $ \mathtt{0} $ or $ \mathtt{1} $ .

## Input Format

Each test contains multiple test cases. The first line of the input 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 10^5 $ ) — the length of $ s $ .

The second line contains the binary string $ s $ of length $ n $ ( $ s_i=\mathtt{0} $ or $ \mathtt{1} $ ).

The third line contains the binary string $ r $ of length $ n-1 $ ( $ r_i=\mathtt{0} $ or $ \mathtt{1} $ ).

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

## Output Format

For each test case, print "YES" (without quotes) if you can win the game, and "NO" (without quotes) otherwise.

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.

## Sample #1

### Sample Input #1

```
6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010
```

### Sample Output #1

```
NO
YES
YES
NO
YES
NO
```

## Hint

In the first test case, you cannot perform the first operation. Thus, you lose the game.

In the second test case, you can choose $ k=1 $ in the only operation, and after that, $ s $ becomes equal to $ \mathtt{1} $ . Thus, you win the game.

In the third test case, you can perform the following operations: $ \mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1} $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, games, strings
Difficulty: 1100
# Set

## Problem Description

You are given a positive integer $ k $ and a set $ S $ of all integers from $ l $ to $ r $ (inclusive).

You can perform the following two-step operation any number of times (possibly zero):

1. First, choose a number $ x $ from the set $ S $ , such that there are at least $ k $ multiples of $ x $ in $ S $ (including $ x $ itself);
2. Then, remove $ x $ from $ S $ (note that nothing else is removed).

Find the maximum possible number of operations that can be performed.

## Input Format

Each test contains multiple test cases. The first line of the input 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 three integers $ l $ , $ r $ , and $ k $ ( $ 1\le l\le r\leq 10^9 $ , $ 1\leq k\le r-l+1 $ ) — the minimum integer in $ S $ , the maximum integer in $ S $ , and the parameter $ k $ .

## Output Format

For each test case, output a single integer — the maximum possible number of operations that can be performed.

## Sample #1

### Sample Input #1

```
8
3 9 2
4 9 1
7 9 2
2 10 2
154 220 2
147 294 2
998 24435 3
1 1000000000 2
```

### Sample Output #1

```
2
6
0
4
0
1
7148
500000000
```

## Hint

In the first test case, initially, $ S = \{3,4,5,6,7,8,9\} $ . One possible optimal sequence of operations is:

1. Choose $ x = 4 $ for the first operation, since there are two multiples of $ 4 $ in $ S $ : $ 4 $ and $ 8 $ . $ S $ becomes equal to $ \{3,5,6,7,8,9\} $ ;
2. Choose $ x = 3 $ for the second operation, since there are three multiples of $ 3 $ in $ S $ : $ 3 $ , $ 6 $ , and $ 9 $ . $ S $ becomes equal to $ \{5,6,7,8,9\} $ .

In the second test case, initially, $ S=\{4,5,6,7,8,9\} $ . One possible optimal sequence of operations is:

1. Choose $ x = 5 $ , $ S $ becomes equal to $ \{4,6,7,8,9\} $ ;
2. Choose $ x = 6 $ , $ S $ becomes equal to $ \{4,7,8,9\} $ ;
3. Choose $ x = 4 $ , $ S $ becomes equal to $ \{7,8,9\} $ ;
4. Choose $ x = 8 $ , $ S $ becomes equal to $ \{7,9\} $ ;
5. Choose $ x = 7 $ , $ S $ becomes equal to $ \{9\} $ ;
6. Choose $ x = 9 $ , $ S $ becomes equal to $ \{\} $ .

In the third test case, initially, $ S=\{7,8,9\} $ . For each $ x $ in $ S $ , no multiple of $ x $ other than $ x $ itself can be found in $ S $ . Since $ k = 2 $ , you can perform no operations.

In the fourth test case, initially, $ S=\{2,3,4,5,6,7,8,9,10\} $ . One possible optimal sequence of operations is:

1. Choose $ x = 2 $ , $ S $ becomes equal to $ \{3,4,5,6,7,8,9,10\} $ ;
2. Choose $ x = 4 $ , $ S $ becomes equal to $ \{3,5,6,7,8,9,10\} $ ;
3. Choose $ x = 3 $ , $ S $ becomes equal to $ \{5,6,7,8,9,10\} $ ;
4. Choose $ x = 5 $ , $ S $ becomes equal to $ \{6,7,8,9,10\} $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, math
Difficulty: 800
# Alice's Adventures in Addition

## Problem Description

Note that the memory limit is unusual.

The Cheshire Cat has a riddle for Alice: given $ n $ integers $ a_1, a_2, \ldots, a_n $ and a target $ m $ , is there a way to insert $ + $ and $ \times $ into the circles of the expression $ $$$a_1 \circ a_2 \circ \cdots \circ a_n = m $ $  to make it true? We follow the usual order of operations:  $ \\times $  is done before  $ +$$$.

Although Alice is excellent at chess, she is not good at math. Please help her so she can find a way out of Wonderland!

## Input Format

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

The first line of each test case contains two integers $ n, m $ ( $ 1\le n\le 2\cdot 10^5 $ ; $ 1\le m\le 10^4 $ ) — the number of integers and the target, respectively.

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

The sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

## Output Format

For each test case, output "YES" without quotes if it is possible to get the target by inserting $ + $ or $ \times $ and "NO" otherwise.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

## Sample #1

### Sample Input #1

```
6
5 4
2 1 1 1 2
5 5
2 1 1 1 2
5 6
2 1 1 1 2
5 7
2 1 1 1 2
5 8
2 1 1 1 2
5 6
2 0 2 2 3
```

### Sample Output #1

```
YES
YES
YES
YES
NO
YES
```

## Hint

Possible solutions for the first four test cases are shown below. $ $$$\begin{align*} 2 \times 1 + 1 \times 1 \times 2 &= 4 \\ 2 \times 1 + 1 + 1 \times 2 &= 5 \\ 2 \times 1 + 1 + 1 + 2 &= 6 \\ 2 + 1 + 1 + 1 + 2 &= 7 \\ \end{align*} $ $  It is impossible to get a result of  $ 8$$$ in the fifth test case.

## Limit



Time Limit
3.00s

Memory Limit
31.25MB

Tags: bitmasks, brute force, dp, implementation
Difficulty: 2700
# Alice's Adventures in the Rabbit Hole

## Problem Description

Alice is at the bottom of the rabbit hole! The rabbit hole can be modeled as a tree $ ^{\text{∗}} $ which has an exit at vertex $ 1 $ , and Alice starts at some vertex $ v $ . She wants to get out of the hole, but unfortunately, the Queen of Hearts has ordered her execution.

Each minute, a fair coin is flipped. If it lands heads, Alice gets to move to an adjacent vertex of her current location, and otherwise, the Queen of Hearts gets to pull Alice to an adjacent vertex of the Queen's choosing. If Alice ever ends up on any of the non-root leaves $ ^{\text{†}} $ of the tree, Alice loses.

Assuming both of them move optimally, compute the probability that Alice manages to escape for every single starting vertex $ 1\le v\le n $ . Since these probabilities can be very small, output them modulo $ 998\,244\,353 $ .

Formally, let $ M = 998\,244\,353 $ . It can be shown that the exact answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .

 $ ^{\text{∗}} $ A tree is a connected simple graph which has $ n $ vertices and $ n-1 $ edges.

 $ ^{\text{†}} $ A leaf is a vertex that is connected to exactly one edge.

## 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 a single integer $ n $ ( $ 2\le n\le 2\cdot 10^5 $ ) — the number of vertices in the tree.

The $ i $ -th of the next $ n - 1 $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ and $ x_i \neq y_i $ ) — the edges of the tree. It is guaranteed that the given edges form a tree.

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 $ integers on one line — the probabilities of Alice escaping starting from vertex $ 1, 2, \ldots, n $ . Since these probabilities can be very small, output them modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
2
5
1 2
1 3
2 4
3 5
9
1 2
2 3
4 5
5 6
7 8
8 9
2 4
5 7
```

### Sample Output #1

```
1 499122177 499122177 0 0 
1 499122177 0 332748118 166374059 0 443664157 720954255 0
```

## Hint

For the first test case:

1. Alice escapes from the root (vertex $ 1 $ ) by definition with probability $ 1 $ .
2. Alice immediately loses from vertices $ 4 $ and $ 5 $ since they are leaves.
3. From the other two vertices, Alice escapes with probability $ \frac 12 $ since the Queen will pull her to the leaves.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, dfs and similar, dp, games, greedy, math, probabilities, trees
Difficulty: 2300
# Alice's Adventures in Cutting Cake

## Problem Description

Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of $ n $ sections with tastiness values $ a_1, a_2, \ldots, a_n $ . There are $ m $ creatures at the tea party, excluding Alice.

Alice will cut the cake into $ m + 1 $ pieces. Formally, she will partition the cake into $ m + 1 $ subarrays, where each subarray consists of some number of adjacent sections. The tastiness of a piece is the sum of tastiness of its sections. Afterwards, she will divvy these $ m + 1 $ pieces up among the $ m $ creatures and herself (her piece can be empty). However, each of the $ m $ creatures will only be happy when the tastiness of its piece is $ v $ or more.

Alice wants to make sure every creature is happy. Limited by this condition, she also wants to maximize the tastiness of her own piece. Can you help Alice find the maximum tastiness her piece can have? If there is no way to make sure every creature is happy, output $ -1 $ .

## 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 three integers $ n, m, v $ ( $ 1\le m\le n\le 2\cdot 10^5 $ ; $ 1\le v\le 10^9 $ ) — the number of sections, the number of creatures, and the creatures' minimum requirement for tastiness, respectively.

The next line contains $ n $ space separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the tastinesses of the sections.

The sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

## Output Format

For each test case, output the maximum tastiness Alice can achieve for her piece, or $ -1 $ if there is no way to make sure every creature is happy.

## Sample #1

### Sample Input #1

```
7
6 2 1
1 1 10 1 1 10
6 2 2
1 1 10 1 1 10
6 2 3
1 1 10 1 1 10
6 2 10
1 1 10 1 1 10
6 2 11
1 1 10 1 1 10
6 2 12
1 1 10 1 1 10
6 2 12
1 1 1 1 10 10
```

### Sample Output #1

```
22
12
2
2
2
0
-1
```

## Hint

For the first test case, Alice can give the first and second section as their own pieces, and then take the remaining $ 10 + 1 + 1 + 10 = 22 $ tastiness for herself. We can show that she cannot do any better.

For the second test case, Alice could give the first and second section as one piece, and the sixth section as one piece. She can then take the remaining $ 10 + 1 + 1 = 12 $ tastiness for herself. We can show that she cannot do any better.

For the seventh test case, Alice cannot give each creature a piece of at least $ 12 $ tastiness.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, dp, greedy, two pointers
Difficulty: 1600
# Alice's Adventures in "Chess"

## Problem Description

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.

## Sample #1

### Sample Input #1

```
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
```

### Sample Output #1

```
YES
NO
YES
YES
YES
NO
```

## Hint

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.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, implementation, math
Difficulty: 900
# The Endspeaker (Easy Version)

## Problem Description

This is the easy version of this problem. The only difference is that you only need to output the minimum total cost of operations in this version. You must solve both versions to be able to hack.

You're given an array $ a $ of length $ n $ , and an array $ b $ of length $ m $ ( $ b_i > b_{i+1} $ for all $ 1 \le i < m $ ). Initially, the value of $ k $ is $ 1 $ . Your aim is to make the array $ a $ empty by performing one of these two operations repeatedly:

- Type $ 1 $ — If the value of $ k $ is less than $ m $ and the array $ a $ is not empty, you can increase the value of $ k $ by $ 1 $ . This does not incur any cost.
- Type $ 2 $ — You remove a non-empty prefix of array $ a $ , such that its sum does not exceed $ b_k $ . This incurs a cost of $ m - k $ .

You need to minimize the total cost of the operations to make array $ a $ empty. If it's impossible to do this through any sequence of operations, output $ -1 $ . Otherwise, output the minimum total cost of the operations.

## Input Format

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

The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 3 \cdot 10^5 $ , $ \boldsymbol{1 \le n \cdot m \le 3 \cdot 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 $ ).

The third line of each test case contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 1 \le b_i \le 10^9 $ ).

It is also guaranteed that $ b_i > b_{i+1} $ for all $ 1 \le i < m $ .

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

## Output Format

For each test case, if it's possible to make $ a $ empty, then output the minimum total cost of the operations.

If there is no possible sequence of operations which makes $ a $ empty, then output a single integer $ -1 $ .

## Sample #1

### Sample Input #1

```
5
4 2
9 3 4 3
11 7
1 2
20
19 18
10 2
2 5 2 1 10 3 2 9 9 6
17 9
10 11
2 2 2 2 2 2 2 2 2 2
20 18 16 14 12 10 8 6 4 2 1
1 6
10
32 16 8 4 2 1
```

### Sample Output #1

```
1
-1
2
10
4
```

## Hint

In the first test case, one optimal sequence of operations which yields a total cost of $ 1 $ is as follows:

- Perform an operation of type $ 2 $ . Choose the prefix to be $ [9] $ . This incurs a cost of $ 1 $ .
- Perform an operation of type $ 1 $ . The value of $ k $ is now $ 2 $ . This incurs no cost.
- Perform an operation of type $ 2 $ . Choose the prefix to be $ [3, 4] $ . This incurs a cost of $ 0 $ .
- Perform an operation of type $ 2 $ . Choose the prefix to be $ [3] $ . This incurs a cost of $ 0 $ .
- The array $ a $ is now empty, and the total cost of all operations is $ 1 $ .

In the second test case, it's impossible to remove any prefix of the array since $ a_1 > b_1 $ , so array $ a $ cannot be made empty by any sequence of operations.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, dp, graphs, greedy, implementation, two pointers
Difficulty: 1700
# Add Zeros

## Problem Description

You're given an array $ a $ initially containing $ n $ integers. In one operation, you must do the following:

- Choose a position $ i $ such that $ 1 < i \le |a| $ and $ a_i = |a| + 1 - i $ , where $ |a| $ is the current size of the array.
- Append $ i - 1 $ zeros onto the end of $ a $ .

After performing this operation as many times as you want, what is the maximum possible length of the array $ a $ ?

## Input Format

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

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

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

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

## Output Format

For each test case, output a single integer — the maximum possible length of $ a $ after performing some sequence of operations.

## Sample #1

### Sample Input #1

```
4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1
```

### Sample Output #1

```
10
11
10
1
```

## Hint

In the first test case, we can first choose $ i = 4 $ , since $ a_4 = 5 + 1 - 4 = 2 $ . After this, the array becomes $ [2, 4, 6, 2, 5, 0, 0, 0] $ . We can then choose $ i = 3 $ since $ a_3 = 8 + 1 - 3 = 6 $ . After this, the array becomes $ [2, 4, 6, 2, 5, 0, 0, 0, 0, 0] $ , which has a length of $ 10 $ . It can be shown that no sequence of operations will make the final array longer.

In the second test case, we can choose $ i=2 $ , then $ i=3 $ , then $ i=4 $ . The final array will be $ [5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0] $ , with a length of $ 11 $ .

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, data structures, dfs and similar, dp, graphs, greedy
Difficulty: 1500