时间线修复

题目描述

在四维空间中，Orange由于过度使用时间调制器，导致时间线发生了紊乱，这导致了四维空间中可能会出现一些非正常的时空碎片，这是在太糟糕了！

我们这里假设时间是一条不断向前延伸的直线，其共包含 $n$ 个时间点，其中其中的时间点不断向前延伸，依次为 $a_1, a_2, a_3, \cdots, a_n$。但是由于Orange的干预，导致其发生了一些异常，例如可能出现多个时间点 $a_i$，也有可能出现 $a_i$，但是不存在 $a_{i-1}$，即 $a_i$ 并不是由时间线向前延伸过来的，而是突然发生时间跳跃而产生的时间点。

Orange知道，在四维空间产生的时间异常会对原来的三维空间造成非常大的影响，因此他必须马上修复这个异常。Orange需要从现有的 $a_n$ 时间点中挑选出一个子序列，用来修复异常的时间。

Orange挑选的时间点必须满足如下要求：

• 我们假设Orange挑选的时间点记为集合 $S$。
• 选择出的时间点必须包含 $1$，因为 $a_1$ 是时间的起点，即 $1 \in S$。
• 所挑选的时间点必须唯一，也就是不应存在选择两个相同的时间点，即 $\forall a_i, a_j(i \ne j) \in S，a_i \ne a_j$。
• 若要挑选 $i$ 时，则需要保证 $i$ 之前所有的时间点 $1, 2, \cdots, i-1$ 都在集合中，即 $\forall j(j 子序列：子序列指的是从原序列中任意删除部分元素，剩下元素相对位置保持不变所构成的序列。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据数。 对于每组测试数据： 第一行为一个整数 $n$，表示时间点的个数。 第二行为 $n$ 个整数 $a_i$，表示各个时间点。

数据范围：

$1 \le n \le 10^5$ $1 \le a_i \le 10^9$ $\sum n \le 2 \times 10^5$

输出格式

对于每组测试数据，输出一行，包含一个整数表示答案。

样例 #1

样例输入 #1

2
5
1 2 1 3 4
3
2 3 4

样例输出 #1

8
0

提示

样例解释1

对于序列 $[1, 2, 1, 3, 4]$ 的所有子序列： 我们可以选择大小为 $1$ 的集合: $[1]$，$[1]$ 我们可以选择大小为 $2$ 的集合：$[1,2]$，$[2,1]$ 我们可以选择大小为 $3$ 的集合: $[1,2,3]$，$[2,1,3]$ 我们可以选择大小为 $4$ 的集合: $[1,2,3,4]$，$[2,1,3,4]$ 可以证明不包含其他选择方法，因此答案为 $8$ 。