题目描述

给定一个包含 $n$ 个正整数的序列 $[a_1, a_2, \ldots, a_n]$。你可以对该序列执行以下操作：

• 操作内容：
  • 选择一个子数组 $a[l \ldots r]$（满足 $1 \leq l < r \leq n$），且该子数组中的元素并不全相同（即存在两个整数 $l \leq i < j \leq r$ 使得 $a_i \neq a_j$）。
  • 将该子数组中的每个元素都更改为子数组中的最大值 $\max\{a_l, a_{l+1}, \ldots, a_r\}$。

目标： 确定可以执行的最大操作次数。

输入格式

• 每个测试用例包含多组数据。
• 第一行包含一个整数 $t$，表示测试用例的数量。（$1 \leq t \leq 1000$）
• 接下来是 $t$ 个测试用例的描述，每个测试例如下：
  • 第一行包含一个整数 $n$，表示序列的长度。（$1 \leq n \leq 2 \times 10^5$）
  • 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, 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

说明

• 示例 1：

  • 输入： 2 1 2
  • 操作步骤：
    1. 选择子数组 $a[1 \ldots 2]$，执行操作后序列变为 $[2, 2]$。
  • 输出： 1

• 示例 2：

  • 输入： 2 2 2
  • 说明： 所有元素相同，无法执行任何操作。
  • 输出： 0

• 示例 4：

  • 输入： 3 1 2 3
  • 操作步骤：
    1. 选择子数组 $a[1 \ldots 2]$，执行操作后序列变为 $[2, 2, 3]$。
    2. 选择子数组 $a[2 \ldots 3]$，执行操作后序列变为 $[2, 3, 3]$。
    3. 选择子数组 $a[1 \ldots 3]$，执行操作后序列变为 $[3, 3, 3]$。
  • 输出： 3