408503: GYM103158 H Annoying posts

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Annoying poststime limit per test1 secondmemory limit per test256 megabytesinputbad-memes.inoutputstandard output

Compo was going through his feed on FB site consisting of Khaled Hamed's posts that decrease people's IQ mixed with different posts that increase the IQ. Sick of this, Compo devised a strategy.

He will open FB at every $$$X-th$$$ minute and read all the posts he hadn't read. It's well known that Compo receives exactly one post per minute. where the $$$i-th$$$ post adds $$$A_i$$$ points to his IQ.

Considering that Compo doesn't need any time to read the posts Choose an $$$X$$$ that will maximize the minimum IQ of a single batch of posts that combo reads at once.

Input

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ the number of test cases.

The first line of each test case contains a number $$$N$$$ $$$(1 \leq N \leq 10^5)$$$.

The second line of each test case contains an integer array $$$A_i$$$ $$$(-10^5 \leq A_i \leq 10^5)$$$.

Output

Print the maximum minimum IQ of a single batch.

ExampleInput
2
6
5 5 -20 -20 5 5
7
1 -5 2 4 5 -3 6
Output
-10
10

Source/Category

加入题单

上一题 下一题 算法标签: