결함이 있는 스크립트

데빈은 링 모양으로 연결된 서버 $n$대를 관리하는 시스템 관리자이다. 서버 $i$에는 음이 아닌 정수 부하 $a_i$가 걸려 있다 ($1 \le i \le n$). 데빈은 모든 서버의 부하를 같게 만들고 싶어 하며, 그 공통 부하를 가능한 한 크게 하려고 한다.

데빈에게는 서버의 부하를 줄이는 스크립트가 있다. 서버 $i$에서 이 스크립트를 실행하면 그 서버의 부하가 2만큼 줄어든다(최소 0까지). 그런데 버그 때문에 서버 $i$에서 실행할 때마다 이전 서버인 $i-1$의 부하가 추가로 1만큼 줄어든다. $i = 1$이면 서버가 링으로 연결되어 있으므로 이전 서버는 서버 $n$이다.

데빈은 0회를 포함해 원하는 만큼 스크립트를 실행할 수 있고, 매번 실행할 서버를 고를 수 있다. 부하가 2 미만인 서버에서도 실행할 수 있고, 이전 서버의 부하가 이미 0이어도 실행할 수 있다. 두 경우 모두 해당 서버의 부하는 0이 된다.

이 스크립트로 모든 서버가 도달할 수 있는 같은 부하의 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $t$($1 \le t \le 10^4$)가 주어진다. 각 테스트 케이스는 서버 수 $n$($2 \le n \le 2 \cdot 10^5$)이 적힌 줄로 시작한다. 다음 줄에는 $a_1, a_2, \ldots, a_n$($0 \le a_i \le 10^9$)이 주어진다.

모든 테스트 케이스의 $n$ 합은 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 달성할 수 있는 같은 부하의 최댓값을 한 줄에 출력한다.

첫 번째 테스트 케이스에서 데빈은 서버 1에서 한 번, 서버 2에서 두 번, 서버 4에서 한 번 스크립트를 실행할 수 있다. 그러면 모든 서버의 부하가 5가 된다.