32919번 - Defective Script 다국어

문제

Devin is a system administrator at a tech company that manages a network of $n$ servers arranged in a ring topology. Each server is handling a certain amount of computational load, represented by a non-negative integer $a_i,ドル where $i$ ranges from 1ドル$ to $n$.

To optimize the network performance and ensure fairness, Devin wants to equalize the load across all servers, making each server handle the same amount of load. He aims to maximize this equal load as much as possible.

Devin has developed a script to reduce the load on any server. When he runs the script on server $i,ドル it is supposed to decrease the load on that server by 2ドル$ units (down to a minimum of zero). However, due to a known bug in the script, every time it's executed on server $i,ドル it inadvertently removes an additional 1ドル$ unit of load from the previous server in the network (server $i-1$). If $i = 1,ドル the previous server is server $n$ (since the servers form a ring).

Devin can run this buggy script any number of times (including zero), each time choosing any server to run it on. He can run the script on a server even if its current load is less than 2ドル$ units, or if the load of the previous server is zero (in both cases the load goes to zero).

Help Devin determine the maximum possible equal load that can be achieved on all servers using his script.

입력

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,ドル denoting the number of servers (2ドル \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n,ドル denoting the amounts of load the servers are handling (0ドル \le a_i \le 10^9$).

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

출력

For each test case, print the maximum possible equal load that can be achieved on all servers.

제한

노트

In the first test case, Devin can run the script once on server 1ドル,ドル twice on server 2ドル,ドル and once on server 4ドル$. As a result, each server will be handling 5ドル$ units of load.