베시는 Farmer John에게 우유 양동이를 이용한 게임을 제안했다. 한 줄로 놓인 \(N\)개의 우유 양동이가 있다. \((2 \le N \le 200,000)\) 왼쪽에서 \(i\)번째 양동이에는 처음에 \(a_i\)갤런의 우유가 들어 있다. \((0 \le a_i \le 10^9)\)

게임은 두 단계로 진행된다.

1단계: Farmer John은 서로 인접한 두 양동이의 위치를 바꿀 수 있다. 원하는 만큼 여러 번 바꿀 수 있지만, 한 번 바꿀 때마다 동전 하나를 사용한다.

2단계: 위치를 모두 바꾼 뒤, 양동이가 하나만 남을 때까지 다음 작업을 반복한다.

• 우유가 각각 \(a_i\), \(a_{i+1}\)갤런 들어 있는 서로 인접한 두 양동이를 고른다.
• 두 양동이를 제거하고, 그 자리에 우유가 \(\frac{a_i+a_{i+1}}{2}\)갤런 들어 있는 양동이 하나를 놓는다.

모든 병합이 끝난 뒤 마지막 양동이에 들어 있는 우유의 양을 최대로 만들려고 한다. 이 최댓값을 달성하기 위해 Farmer John이 1단계에서 사용해야 하는 동전의 최소 개수를 구하여라.

입력

첫째 줄에 서로 독립적인 테스트 케이스의 수 \(T\)가 주어진다. \((1 \le T \le 100)\)

각 테스트 케이스의 첫째 줄에 양동이의 수 \(N\)이 주어진다.

각 테스트 케이스의 둘째 줄에 \(N\)개의 정수 \(a_1,a_2,\dots,a_N\)이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대한 \(N\)의 합은 \(500,000\) 이하이다.

출력

각 테스트 케이스마다 마지막 양동이의 우유 양을 최대로 만들기 위해 필요한 동전의 최소 개수를 한 줄에 하나씩 출력한다.

예제 입력 1

2
3
0 0 1
3
0 1 0

예제 출력 1

0
1

예제 설명 1

첫 번째 테스트 케이스에서는 1단계에서 양동이의 위치를 바꿀 필요가 없다. 2단계에서 첫 두 양동이를 병합한 뒤 남은 두 양동이를 병합하면 최종 우유 양은 \(0.5\)가 되며, 이 값이 최댓값이다.

두 번째 테스트 케이스에서는 1단계에서 첫 번째와 두 번째 양동이의 위치를 한 번 바꾸어야 2단계에서 최종 우유 양 \(0.5\)를 달성할 수 있다. 위치를 바꾸지 않고는 \(0.5\)를 달성할 수 없다.

예제 입력 2

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

예제 출력 2

1
2
0
3

예제 설명 2

첫 번째 테스트 케이스에서 Farmer John은 1단계에 두 번째와 세 번째 양동이의 위치를 바꿀 수 있다. 이후 2단계는 다음과 같이 진행할 수 있다.

[9,9,4,2]
-> 세 번째와 네 번째 양동이 병합
[9,9,3]
-> 두 번째와 세 번째 양동이 병합
[9,6]
-> 첫 번째와 두 번째 양동이 병합
[7.5]

최종 우유 양은 \(7.5\)이며, 이는 가능한 최댓값이다. 위치를 더 많이 바꾸어도 최종 우유 양을 \(7.5\)보다 크게 만들 수 없고, 더 적게 바꾸면 \(7.5\)에 도달할 수 없다.

출처

USACO 2026 First Contest, Gold, Problem 2. Milk Buckets