4342: (2008珠海赛) Water Tanks

[提交][状态][讨论版][命题人:]

题目描述

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 ﬂow 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 ﬁnal one between 1 and 10). Your task is to ﬁnd the minimal number of valves to be opened, to equalize all water levels in each tank.

输入

The ﬁrst 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


[提交][状态]