STO  Stockade
Original problem statement (in Polish) can be found here.
The year is 50 B.C. Gaul is entirely occupied by the Romans. Well, not entirely! One small village of indomitable Gauls still holds out against the invaders. And life is not easy for the Roman legionaries who garrison the fortified camps of Totorum, Aquarium, Laudanum and Compendium...
The year is 49 B.C. Gaul is entirely occupied by the Romans. Well, no one could seriously expect one small village to resist the mighty army of the great Roman Empire. Fortunately, thanks to Julius Caesar's infinite generosity (Ave Caesar!), the settlement wasn't razed to the ground. There was no other choice for the villagers than to conform to the new authorities.
But some of the rules of Roman law can be downright ridiculous. As it turns out, even heights of individual stakes in the stockade encircling the village are strictly regulated. Here is an excerpt from the law, laid down by Roman clerks, and approved by the great ruler, Gaius Julius Caesar (Ave Caesar!):
 Every stockade encircling every village in the whole Roman Empire (governed justly by the great Julius Caesar) should have even number of wooden logs.
 Every log in every stockade should have some minimum height, specified in "Weights and Measures Act", article 15, passage 9. Moreover, the logs can be at most 1000 quarters of a sicilicus^{1} higher than this minimum height.
 For every log, the adjacent logs have to be both higher or both lower. It symbolizes the harmony in the whole Roman Empire, governed justly by the great Julius Caesar (Ave Caesar!).
^{1}sicilicus  Roman unit of length, equal to 1/48 of Roman foot.
As one might expect, stockade around the village of indomitable Gauls did not meet the requirements  specifically, it violated the last rule (it did satisfy the first two, though). Now, the villagers have to lower or raise some of the logs, but this is a lot of work. Determine the minimum number of logs that have to be lowered or raised, so that the final stockade will satisfy the rule of harmony.
Input
The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.
Each testcase consist of a single line. It begins with an integer n, indicating the number of logs in the stockade. (2 <= n <= 10^{6}, 2  n), followed by n integers x_{i}, indicating the difference between the height of the ith log and the minimal possible height, expressed in quarters of a sicilicus (0 <= x_{i} <= 1000). ith log is adjacent to (i+1)th log, moreover, first log is adjacent to the last log (stockade encircles the village).
Output
For every testcase you should output one integer  minimum number of logs that have to be lowered or raised, so that the stockade satisfies the requirements of Roman law.
Example
Input:
3 6 1 2 3 4 5 6 6 1 2 1 2 1 2 6 2 2 2 2 2 2
Output:
2 0 3
Explanation
In the first case it is enough to lower the third and the fifth log to height 1. In the second case, the stockade already satisfies all the rules. (Ave Caesar!)
hide comments
Piotr Jagie³³o:
20160406 22:39:36
Correct output for the testcase you posted is 2. 

Baojun Wang:
20160406 21:37:17
what is the minimum height? Is it 0 or 1? what's the expected output for case such as:

Added by:  Piotr Jagiełło 
Date:  20160405 
Time limit:  1s5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  PIZZA 2015 qualifying round 