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.

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

```
3
2
5
```