问题 4342 --(2008珠海赛) Water Tanks

4342: (2008珠海赛) Water Tanks

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

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

来源

[提交][状态]