给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
当数组不为空时,将执行一个由两个步骤组成的操作:
- 首先选择数组中的最大元素(如果有多个最大元素,则选择最右边的最大值);
- 然后,所选元素之后的所有元素, 包括它,从数组中删除。
您的任务是计算数组变空之前将执行的操作数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 将执行的操作数。
示例
输入复制
452 1 2 3 161 2 3 4 5 633 2 141 3 3 1
输出复制
3613
注意
在第一个示例中,数组为 $$$[2, 1, 2, 3, 1]$$$。对其进行以下操作:
- 首先,选择第 $$$4$$$ 个元素。最后两个元素被移除,数组变为$$$[2, 1, 2]$$$;
- 然后,选择$$$3$$$-rd 元素。最后一个元素被移除,数组变为$$$[2, 1]$$$;
- 然后,选择$$$1$$$-st 元素。两个元素都被删除,因此在 $$$3$$$ 操作后数组变为空。