SP26790 STO - Stockade

给定一个长度为偶数的数列 $A$，你需要改变 $A$ 中的某些数，使得对于 $A$ 中的每一个数，在 $A$ 中与之相邻的两个数必须都大于或都小于这个数。 你需要求出需要改变的数的最少个数。 **注意，$A$ 是环形的，也就是说数列中的第一个数与最后一个数相邻。**

第一行一个正整数 $T$。表示测试数据组数。 接下来 $T$ 行，每行描述一组测试数据。 对于每组测试数据，先给出一个整数 $n$，再给出 $n$ 个数，表示 $A$。

对于每组测试数组，输出一行一个数，表示需要改变的数的最少个数。

$1\le n\le 10^6,2|n，0\le A_i\le 10^3$。 对于每一个测试点，保证 $\sum n\le 10^6$。 Translated by \_Ponder_