题目翻译

题目描述

给定一个长度为 $n$ 的正整数序列 $[a_1, a_2, ..., a_n]$。你可以对该序列执行以下操作：

• 选择一个子数组 $a[l...r]$（满足 $1 \leq l < r \leq n$），要求该子数组中并非所有元素都相同（即存在整数 $l \leq i < j \leq r$，使得 $a_i \neq a_j$）。
• 将这个子数组中的每个元素都修改为该子数组的最大值 $max_{l \leq i \leq r} a_i$。

请你确定最多可以执行多少次这样的操作。

输入格式

输入包含多组测试用例。第一行给出测试用例的数量 $t$（$1 \leq t \leq 1000$）。 每组测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$）。

所有测试用例的 $n$ 之和不超过 $4 \times 10^5$。

输出格式

对于每组测试用例，输出最多可以执行的操作次数。

样例

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

1
0
3
3

提示

• 第一组测试用例的最优操作序列：选择子数组 $a[1...2]$ 执行操作，序列变为 $[2, 2]$，共 1 次操作。
• 第二组测试用例中，无法执行任何操作（子数组必须满足“元素不全相同”的条件）。
• 第四组测试用例的最优操作序列：
  1. 选择子数组 $a[1...2]$ 执行操作，序列变为 $[2, 2, 3]$；
  2. 选择子数组 $a[2...3]$ 执行操作，序列变为 $[2, 3, 3]$；
  3. 选择子数组 $a[1...3]$ 执行操作，序列变为 $[3, 3, 3]$； 共 3 次操作。