#5011. [Jx2017]颜色

内存限制:512 MiB 时间限制:30 Sec

题目描述

可怜有一个长度为n的正整数序列Ai,其中相同的正整数代表着相同的颜色。
现在可怜觉得这个序列太长了,于是她决定选择一些颜色把这些颜色的所有位置都删去。
删除颜色i可以定义为把所有满足Aj=i的位置j都从序列中删去。
然而有些时候删去之后,整个序列变成了好几段,可怜不喜欢这样,于是她想要知道有多
少种删去颜色的方案使得最后剩下来的序列非空且连续。
例如颜色序列{1,2,3,4,5},删除颜色3后序列变成了{1,2}和{4,5}两段,不满足条件。
而删除颜色1后序列变成了{2,3,4,5},满足条件。
两个方案不同当且仅当至少存在一个颜色i只在其中一个方案中被删去。
 。

输入格式

第一行输入一个整数T表示数据组数。
每组数据第一行输入一个整数n表示数列长度。
第二行输入n个整数描述颜色序列。
1 ≤ T, ∑ n ≤ 3 × 10^5, 1 ≤ Ai ≤ n

输出格式

对于每组数据输出一个整数表示答案

样例

样例输入


			
1
5
1 3 2 4 3

样例输出


			
6
//满足条件的删颜色方案有 {1}, {1, 3}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, ∅

数据范围与提示

为试题的完整性,下面给出Jxoi2017题面及前两题数据www.lydsy.com/JudgeOnline/upload/jxoi2017.rar