问题 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 ﬂ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

## 来源

[提交][状态]