Fun with Even Subarrays
Contest: Codeforces Round 768 (Div. 2)
Difficulty rating: 1100
Tags: dp, greedy

You are given an array $$$a$$$ of $$$n$$$ elements. You can apply the following operation to it any number of times:

- Select some subarray from $$$a$$$ of even size $$$2k$$$ that begins at position $$$l$$$ ($$$1\le l \le l+2\cdot{k}-1\le n$$$, $$$k \ge 1$$$) and for each $$$i$$$ between $$$0$$$ and $$$k-1$$$ (inclusive), assign the value $$$a_{l+k+i}$$$ to $$$a_{l+i}$$$.

For example, if $$$a = [2, 1, 3, 4, 5, 3]$$$, then choose $$$l = 1$$$ and $$$k = 2$$$, applying this operation the array will become $$$a = [3, 4, 3, 4, 5, 3]$$$.

Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
Print $$$t$$$ lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test, all elements are equal, therefore no operations are needed.

In the second test, you can apply one operation with $$$k=1$$$ and $$$l=1$$$, set $$$a_1 := a_2$$$, and the array becomes $$$[1, 1]$$$ with $$$1$$$ operation.

In the third test, you can apply one operation with $$$k=1$$$ and $$$l=4$$$, set $$$a_4 := a_5$$$, and the array becomes $$$[4, 4, 4, 4, 4]$$$.

In the fourth test, you can apply one operation with $$$k=1$$$ and $$$l=3$$$, set $$$a_3 := a_4$$$, and the array becomes $$$[4, 2, 3, 3]$$$, then you can apply another operation with $$$k=2$$$ and $$$l=1$$$, set $$$a_1 := a_3$$$, $$$a_2 := a_4$$$, and the array becomes $$$[3, 3, 3, 3]$$$.

In the fifth test, there is only one element, therefore no operations are needed.

Example input:
5
3
1 1 1
2
2 1
5
4 4 4 2 4
4
4 2 1 3
1
1

Example output:
0
1
1
2
0

Editorial:
For simplicity, let $$$b_1, b_2, ..., b_n = a_n, a_{n-1}, ..., a_1$$$ (let $$$b$$$ be $$$a$$$ reversed). The operation transforms to select a subarray $$$[l, r]$$$ of length $$$2\cdot{k}$$$, so $$$k = \frac{r-l+1}{2}$$$, then for all $$$i$$$ such that $$$0 \leq i < k$$$, set $$$b_{l+k+i} = b_{l+i}$$$.
$$$b_1$$$ can not be changed with the given operation. That reduces the problem to make all elements equal to $$$b_1$$$.
Let $$$x$$$ be the rightmost index such that for all $$$1 \leq i \leq x$$$, $$$b_i = b_1$$$ holds.
The problem will be solved when $$$x = n$$$.
If an operation is applied with $$$l + k > x + 1$$$, $$$b_{x+1}$$$ will not change and $$$x$$$ will remain the same.
The largest range with $$$l + k \leq x + 1$$$ is $$$[1, 2\cdot{x}]$$$, applying an operation to it will lead to $$$b_{x+1}, b_{x+2}, ..., b_{2\cdot{x}} = b_1, b_2, ..., b_x$$$, so $$$x$$$ will become at least $$$2\cdot{x}$$$ and there is not any other range that will lead to a bigger value of $$$x$$$.
If $$$2\cdot{x} > n$$$, it is possible to apply the operation on $$$[x-(n-x)+1,n]$$$, after applying it $$$b_{x+1}, ..., b_n = b_{x-(n-x)+1}, ..., b_x$$$ and all elements will become equal.
The problem can now be solved by repeatedly finding $$$x$$$ and applying the operation on $$$[1, 2\cdot{x}]$$$ or on $$$[x-(n-x)+1,n]$$$ if $$$2\cdot{x} > n$$$.
Since $$$x$$$ will become at least $$$2\cdot{x}$$$ in each operation but the last one, the naive implementation will take $$$O(n\log{n})$$$, however, it is easy to implement it in $$$O(n)$$$.