1631B.md (2331B)
1 Source: https://codeforces.com/problemset/problem/1631/B 2 3 B. Fun with Even Subarrays 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ of $n$ elements. You can apply the following operation to it any number of times: 22 23 * 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}$. 24 25 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]$. 26 27 Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal. 28 29 Input 30 31 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. 32 33 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array. 34 35 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$. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 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. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 3 51 52 1 1 1 53 54 2 55 56 2 1 57 58 5 59 60 4 4 4 2 4 61 62 4 63 64 4 2 1 3 65 66 1 67 68 1 69 ``` 70 71 Output 72 73 ``` 74 0 75 1 76 1 77 2 78 0 79 ``` 80 81 Note 82 83 In the first test, all elements are equal, therefore no operations are needed. 84 85 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. 86 87 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]$. 88 89 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]$. 90 91 In the fifth test, there is only one element, therefore no operations are needed.