1974C.md (2221B)
1 Source: https://codeforces.com/problemset/problem/1974/C 2 3 C. Beautiful Triple Pairs 4 5 time limit per test 6 7 4 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 Polycarp was given an array $a$ of $n$ integers. He really likes triples of numbers, so for each $j$ ($1 \le j \le n - 2$) he wrote down a triple of elements $[a_j, a_{j + 1}, a_{j + 2}]$. 22 23 Polycarp considers a pair of triples $b$ and $c$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied: 24 25 * $b_1 \ne c_1$ and $b_2 = c_2$ and $b_3 = c_3$; 26 * $b_1 = c_1$ and $b_2 \ne c_2$ and $b_3 = c_3$; 27 * $b_1 = c_1$ and $b_2 = c_2$ and $b_3 \ne c_3$. 28 29 Find the number of beautiful pairs of triples among the written triples $[a_j, a_{j + 1}, a_{j + 2}]$. 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array. 38 39 It is guaranteed that the sum of the values of $n$ for all test cases in the test does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $[a_j, a_{j + 1}, a_{j + 2}]$. 44 45 Note that the answer may not fit into 32-bit data types. 46 47 Example 48 49 Input 50 51 ``` 52 8 53 54 5 55 56 3 2 2 2 3 57 58 5 59 60 1 2 1 2 1 61 62 8 63 64 1 2 3 2 2 3 4 2 65 66 4 67 68 2 1 1 1 69 70 8 71 72 2 1 1 2 1 1 1 1 73 74 7 75 76 2 1 1 1 1 1 1 77 78 6 79 80 2 1 1 1 1 1 81 82 5 83 84 2 1 1 1 1 85 ``` 86 87 Output 88 89 ``` 90 2 91 0 92 3 93 1 94 8 95 4 96 3 97 2 98 ``` 99 100 Note 101 102 In the first example, $a = [3, 2, 2, 2, 3]$, Polycarp will write the following triples: 103 104 1. $[3, 2, 2]$; 105 2. $[2, 2, 2]$; 106 3. $[2, 2, 3]$. 107 108 The beautiful pairs are triple $1$ with triple $2$ and triple $2$ with triple $3$. 109 110 In the third example, $a = [1, 2, 3, 2, 2, 3, 4, 2]$, Polycarp will write the following triples: 111 112 1. $[1, 2, 3]$; 113 2. $[2, 3, 2]$; 114 3. $[3, 2, 2]$; 115 4. $[2, 2, 3]$; 116 5. $[2, 3, 4]$; 117 6. $[3, 4, 2]$; 118 119 The beautiful pairs are triple $1$ with triple $4$, triple $2$ with triple $5$, and triple $3$ with triple $6$.