Problem2208--Water Tanks

2208: Water Tanks

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]


You have n identical water tanks arranged in a circle on the ground. Each tank is connected with two
neighbors by a pipe with a valve. All valves are initially closed, so water in each tank cannot move. But
if all the valves are opened, water can flow freely among all the tanks. After some time, all the water
levels will eventually equalize.
However, in many cases, only few valves need to be opened to equalize the water levels. For example, if
the initial water levels are 10, 3, 5, 4, 1, 1, only 3 valves need to be opened (one valve between 3 and 5,
another valve between 1 and 1, and the final one between 1 and 10).
Your task is to find the minimal number of valves to be opened, to equalize all water levels in each tank.


The first line contains t (1<=t<=20), the number of test cases followed. Each test case begins with one
integer n(3<=n<=200), followed by n non-negative integers not greater than 100, the initial water levels.


For each test case, print the minimal number of valves to be opened.

Sample Input Copy

6 10 3 5 4 1 1
4 4 4 3 3
8 2 1 1 2 2 1 1 6

Sample Output Copy