2033C.md (2421B)
1 Source: https://codeforces.com/problemset/problem/2033/C 2 3 C. Sakurako's Field Trip 4 5 time limit per test 6 7 2 seconds 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 Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index $i$ has some topic of interest which is described as $a_i$. As a teacher, you want to minimise the disturbance of the line of students. 22 23 The disturbance of the line is defined as the number of neighbouring people with the same topic of interest. In other words, disturbance is the number of indices $j$ ($1 \le j \lt n$) such that $a_j = a_{j + 1}$. 24 25 In order to do this, you can choose index $i$ ($1\le i\le n$) and swap students at positions $i$ and $n-i+1$. You can perform any number of swaps. 26 27 Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times. 28 29 Input 30 31 The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. 32 33 Each test case is described by two lines. 34 35 * The first line contains one integer $n$ ($2 \le n \le 10^5$) — the length of the line of students. 36 * The second line contains $n$ integers $a_i$ ($1\le a_i\le n$) — the topics of interest of students in line. 37 38 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$. 39 40 Output 41 42 For each test case, output the minimal possible disturbance of the line that you can achieve. 43 44 Example 45 46 Input 47 48 ``` 49 9 50 51 5 52 53 1 1 1 2 3 54 55 6 56 57 2 1 2 2 1 1 58 59 4 60 61 1 2 1 1 62 63 6 64 65 2 1 1 2 2 4 66 67 4 68 69 2 1 2 3 70 71 6 72 73 1 2 2 1 2 1 74 75 5 76 77 4 5 5 1 5 78 79 7 80 81 1 4 3 5 1 1 3 82 83 7 84 85 3 1 3 2 2 3 3 86 ``` 87 88 Output 89 90 ``` 91 1 92 2 93 1 94 0 95 0 96 1 97 1 98 0 99 2 100 ``` 101 102 Note 103 104 In the first example, it is necessary to apply the operation to $i=2$, thus the array will become $[1, \textbf{2}, 1, \textbf{1}, 3]$, with the bold elements indicating those that have swapped places. The disturbance of this array is equal to $1$. 105 106 In the fourth example, it is sufficient to apply the operation to $i=3$, thus the array will become $[2, 1, \textbf{2}, \textbf{1}, 2, 4]$. The disturbance of this array is equal to $0$. 107 108 In the eighth example, it is sufficient to apply the operation to $i=3$, thus the array will become $[1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]$. The disturbance of this array is equal to $0$.