Make Max

题目描述

You are given a sequence of $n$ positive integers $[a_1, . . . , a_n]$. You can apply the following operation to the sequence: • Select a subarray $a[l . . . r]$ $(1 ≤ l < r ≤ n)$ where not all elements are identical (i.e., there exist two integers $l ≤ i < j ≤ r$ such that $a_i \neq a_j$), and then change every element in this subarray to $max_{l≤i≤r} a_i$. Determine the maximum number of such operations that can be performed.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t (1 ≤ t ≤ 1000)$. Description of the test cases follows. The first line of each test case contains an integer $n (1 ≤ n ≤ 2 × 10^5$). The second line of each test case contains n integers $a_1, . . . , a_n (1 ≤ a_i ≤ 10^9)$. The sum of n over all test cases does not exceed $4 × 10^5$.

输出格式

For each test case, print the maximum number of operations that can be performed.

样例 #1

样例输入 #1

4
2
1 2
2
2 2
7
1 1 1 2 2 2 2
3
1 2 3

样例输出 #1

1
0
3
3

提示

In the first test case, an optimal sequence of operations is:

1. Select $a[1 . . . 2]$ and apply the operation, so that a becomes $[2, 2]$.

In the second test case, no operation can be performed. In the fourth test case, an optimal sequence of operations is:

1. Select $a[1 . . . 2]$ and apply the operation, so that a becomes $[2, 2, 3]$.
2. Select $a[2 . . . 3]$ and apply the operation, so that a becomes $[2, 3, 3]$.
3. Select $a[1 . . . 3]$ and apply the operation, so that a becomes $[3, 3, 3]$.