[Solution] Unequal Array solution codeforces

Unequal Array solution codeforces – You are given an array 𝑎a of length 𝑛n. We define the equality of the array as the number of indices 1𝑖𝑛11≤i≤n−1 such that 𝑎𝑖=𝑎𝑖+1ai=ai+1. We are allowed to do the following operation:

[Solution] Unequal Array solution codeforces

  • Select two integers 𝑖i and 𝑥x such that 1𝑖𝑛11≤i≤n−1 and 1𝑥1091≤x≤109. Then, set 𝑎𝑖ai and 𝑎𝑖+1ai+1 to be equal to 𝑥x.

Find the minimum number of operations needed such that the equality of the array is less than or equal to 11.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer 𝑛n (2𝑛21052≤n≤2⋅105) — the length of array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — elements of the array.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105

Output

For each test case, print the minimum number of operations needed.

[Solution] Unequal Array solution codeforces

Example
input

Copy
4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4
output

Copy
2
1
2
0

Unequal Array solution codeforces

In the first test case, we can select 𝑖=2i=2 and 𝑥=2x=2 to form [1,2,2,1,1][1,2,2,1,1]. Then, we can select 𝑖=3i=3 and 𝑥=3x=3 to form [1,2,3,3,1][1,2,3,3,1].

In the second test case, we can select 𝑖=3i=3 and 𝑥=100x=100 to form [2,1,100,100,2][2,1,100,100,2].

For Solution

Click here

Leave a Comment