CF2153D Not Alone

A circular array $ b $ of length $ m $ is nice if every element has at least one adjacent element $ ^{\text{∗}} $ that is equal to it. Formally, for every $ 1\le i\le m $ , at least one of the following holds: $ b_i = b_{(i+m-2)\bmod m\;+1} $ , or $ b_i = b_{i\bmod m\;+1} $ , where $ x \bmod y $ denotes the remainder from dividing $ x $ by $ y $ . You are given a circular array $ a $ of length $ n $ . In one operation, you may increase or decrease any element of $ a $ by $ 1 $ . Your task is to determine the minimum number of operations required to make array $ a $ nice. More formally, find the minimum value of $ \sum_{i=1}^n |b_i - a_i| $ among all nice circular arrays $ b $ of length $ n $ . $ ^{\text{∗}} $ In a circular array of length $ m $ : - For each index $ 2\le i\le m - 1 $ , the element at index $ i $ is adjacent to the elements at indices $ i - 1 $ and $ i + 1 $ . - The element at index $ 1 $ is adjacent to the elements at indices $ 2 $ and $ m $ . - The element at index $ m $ is adjacent to the elements at indices $ m - 1 $ and $ 1 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 3\le n\le 2\cdot 10^5 $ ) — the length of the circular array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1\le a_i\le 10^9 $ ) — the elements of the circular array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output a single integer representing the minimum number of operations required to make array $ a $ nice.

In the first test case, all elements of $ a $ are equal. Therefore, the circular array $ a $ is already nice and no operations are required. In the second test case, we can perform the following sequence of operations: - Increase $ a_1 $ by $ 1 $ . Now, $ a=[3, 100, 99, 3] $ . - Decrease $ a_2 $ by $ 1 $ . Now, $ a=[3, 99, 99, 3] $ . After these operations, every element has at least one adjacent element with the same value: - $ a_1 $ is equal to $ a_4 $ . - $ a_2 $ is equal to $ a_3 $ . - $ a_3 $ is equal to $ a_2 $ . - $ a_4 $ is equal to $ a_1 $ . In the third test case, the circular array $ a $ can become nice by decreasing $ a_4 $ four times. This results in $ a = [2, 2, 5, 5, 5] $ which is nice as every element has at least one adjacent element with the same value.