용

하늘을 나는 용의 삶은 고달프다. 길고 깊은 골짜기에는 목초지가 한 줄로 늘어서 있고, 왼쪽부터 $1, 2, \dots, n$번으로 번호가 매겨져 있다. $i$번 목초지에는 양이 $a_i$마리 있다.

용의 명예 규범은 하루에 단 한 번의 만찬만 허락한다. 만찬이란 목초지 하나를 골라 그곳의 양을 남김없이 먹어 치우는 것이다.

골짜기의 양쪽 비탈은 너무 높아 용조차 넘을 수 없다. 그래서 용은 골짜기를 따라서만 날 수 있으며, 매일 왼쪽 끝과 오른쪽 끝 중 어느 쪽에서 들어올지 스스로 고를 수 있다. 용이 $x$번 목초지의 양을 먹기 위해 날아 들어오면, 지나쳐 온 목초지들, 즉 왼쪽에서 들어왔다면 $1 \dots x-1$번, 오른쪽에서 들어왔다면 $x+1 \dots n$번 목초지의 양들은 모두 놀라 달아나 다시는 돌아오지 않는다.

게다가 매일 하루가 끝날 때마다, 늑대와 질병, 도망, 그리고 용에 대한 소문 때문에 모든 목초지의 양이 각각 $1$마리씩 줄어든다.

용은 가장 큰 목초지의 양이 줄어드는 것을 지켜보며 차례차례 습격하는 편이 나은지, 아니면 큰 곳부터 노리되 지나는 길의 작은 목초지들을 흩어 버리는 편이 나은지 고민에 빠졌다. 결국 용은 이 문제를 현대적인 방식으로 풀기로 하고 당신에게 프로그램을 주문했다.

용이 먹을 수 있는 양의 최대 마릿수를 구하라. 하루가 $t$일째일 때(첫 만찬이 $1$일째) 어떤 목초지를 먹으면 얻는 양은 그 목초지의 원래 마릿수에서 $t-1$을 뺀 값이다.

첫 번째 줄에 데이터 집합의 개수 $z$가 주어진다. 이어서 $z$개의 데이터 집합이 차례로 주어진다.

각 데이터 집합은 한 줄로 이루어진다. 줄의 맨 앞에는 목초지의 개수 $k$ ($1 \le k \le 10000$)가 오고, 그 뒤에 공백으로 구분된 $k$개의 정수가 온다. 각 정수는 해당 목초지의 양의 마릿수로 $0$ 이상 $100000$ 이하이다.

각 데이터 집합마다 용이 먹을 수 있는 양의 최대 마릿수를 한 줄에 하나씩 출력한다.