Codeforces Round 982 (Div. 2) |
---|
Finished |
You're given an array $$$a$$$ initially containing $$$n$$$ integers. In one operation, you must do the following:
After performing this operation as many times as you want, what is the maximum possible length of the array $$$a$$$?
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$$$.
For each test case, output a single integer — the maximum possible length of $$$a$$$ after performing some sequence of operations.
452 4 6 2 555 4 4 5 146 8 2 311
10 11 10 1
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$$$.
Name |
---|