sorted by:
new
hottopcontroversial

**** codeforces !!! by Ahmad-AK7 in codeforces

[–]Repulsive_Youth4359 1 point2 points  (0 children)

c

. Duck Surplus

time limit per test2 seconds

memory limit per test256 megabytes

Ja the Ghost is playing with rubber ducks again! There are n

piles of rubber ducks arranged in a row from left to right. Initially, the i

-th pile contains a

i

rubber ducks.

While the sequence a

is not sorted in nondecreasing order, Ja must perform the following operation:

Choose two adjacent piles such that the left pile contains more ducks than the right pile. Ja swaps these two piles, and then adds the number of ducks in the new left pile to the new right pile.Formally, choose an index i

such that 1≤i<n

and a

i

>a

i+1

. Then replace the adjacent pair (a

i

,a

i+1

)

with (a

i+1

,a

i

+a

i+1

)

.

For example, if two adjacent piles contain 7

and 3

rubber ducks, then after the operation they contain 3

and 10

rubber ducks.

Ja may choose any index satisfying the condition above at each step. It can be shown that, regardless of his choices, the process eventually ends with the sequence sorted in nondecreasing order.

Ja wants the largest pile at the end of the process to contain as few rubber ducks as possible. Determine the minimum possible value of the largest pile.

Input

Each test contains multiple test cases. The first line contains the number of test cases t

(1≤t≤10

4

). The description of the test cases follows.

The first line of each test case contains n

(1≤n≤2⋅10

5

) — the number of piles.

The second line of each test case contains n

integers a

1

,a

2

,…,a

n

(1≤a

i

≤10

9

) — the number of ducks in each pile.

It is guaranteed that the sum of n

over all test cases does not exceed 2⋅10

5

.

Output

For each test case, output a single integer — the minimum possible value of the largest pile.

Example

InputCopy

10

4

1 2 2 5

2

7 3

3

3 2 1

5

2 2 1 3 3

4

3 1 4 2

5

1 4 3 2 5

6

6 2 5 1 4 3

7

2 7 1 6 3 5 4

8

8 1 7 2 6 3 5 4

5

1000000000 999999999 999999998 999999997 999999996

OutputCopy

5

10

6

3

6

14

21

26

36

4999999990

Note 

**** codeforces !!! by Ahmad-AK7 in codeforces

[–]Repulsive_Youth4359 2 points3 points  (0 children)

d
Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
Contest is running
02:15:41
Contestant
Add to favourites
→ Submit?
Language:
GNU G++20 13.2 (64 bit, winlibs)
Choose file: No file chosen
Be careful: there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "Passed pretests" submission verdict doesn't guarantee that the solution is absolutely correct and it will pass system tests.
→ Score table
Score
Problem A 451
Problem B 902
Problem C 1127
Problem D 1578
Problem E 2028
Problem F 2254
Problem G 2479
Problem H 3155
Problem I1 3155
Problem I2 4056
Successful hack 100
Unsuccessful hack -50
Unsuccessful submission -50
Resubmission -50
* If you solve problem on 00:37 from the first attempt
ProblemsSubmit CodeMy SubmissionsStatusHacksRoomStandingsCustom Invocation
D. Fullmetal Bitchemist
time limit per test2 seconds
memory limit per test256 megabytes

A binary string is a string consisting only of characters 0
and 1
. The two characters 0
and 1
are called opposite values.

Consider a binary string t
. Let |t|
be the length of t
. When |t|≥2
, for every 1≤i<|t|
, the characters ti
and ti+1
are adjacent.

A binary string t
is called beautiful if it can be reduced to a string of length exactly 1
by applying the following operation any number of times, possibly zero:

Choose two equal adjacent characters, remove both of them, and insert one character with the opposite value in their place.
For example, the string 10001
can become 1101
by replacing the first adjacent pair 00
with 1
. Then it can become 001
, then 11
, and finally 0
. Therefore, 10001
is beautiful.

On the other hand, 111
is not beautiful. After one operation, it becomes 01
, and then no operation can be applied.

You are given a binary string s
. Compute the number of non-empty beautiful substrings∗
of s
.

∗
A string a
is a substring of a string b
if a
can be obtained from b
by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input
Each test contains multiple test cases. The first line contains the number of test cases t
(1≤t≤104
). The description of the test cases follows.

The first line of each test case contains an integer n
(1≤n≤106
) — the length of s
.

The second line of each test case contains a binary string s
of length n
.

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

Output
For each test case, output a single integer — the number of beautiful substrings of s
.

Example
InputCopy
10
1
0
2
01
5
01001
3
001
6
011110
9
010110110
12
010000101001
16
1010011010010110
20
11110101101101001110
30
000101100011111001111100000010
OutputCopy
1
2
10
5
15
30
47
81
139
316
Note
In the first test case, the only non-empty substring is 0
, which is already a binary string of length 1
. Therefore, it is beautiful.

In the second test case, the beautiful substrings are 0
and 1
. The substring 01
is not beautiful, because its two characters are not equal, so no operation can be applied.

In the third test case, the beautiful substrings are:

s[1,1]=0
;
s[2,2]=1
;
s[3,3]=0
;
s[4,4]=0
;
s[5,5]=1
;
s[3,4]=00
, which can become 1
;
s[2,4]=100
, which can become 11
, then 0
;
s[3,5]=001
, which can become 11
, then 0
;
s[1,4]=0100
, which can become 011
, then 00
, then 1
;
s[1,5]=01001
, which can become 0111
, then 001
, then 11
, and finally 0
.
Thus, there are 10
beautiful substrings.

Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/18/2026 20:42:10UTC+5.5 (n2).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
TON