TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4605
  • Problem
  • P4605【JXOI2017】颜色
    Limits : Time Limit : 10000 MS   Memory Limit : 565535 KB
    Judgment Tips : 1s,512m
    Description

    可怜有一个长度为 n 的正整数序列 Ai,其中相同的正整数代表着相同的颜色。现在可怜觉得这个序列太长了,于是她决定选择一些颜色把这些颜色的所有位置都删去。删除颜色 i 可以定义为把所有满足 Aj = i 的位置 j 都从序列中删去。

    然而有些时候删去之后,整个序列变成了好几段,可怜不喜欢这样,于是她想要知道有多少种删去颜色的方案使得最后剩下来的序列非空且连续。

    例如颜色序列 {1, 2, 3, 4, 5},删除颜色 3 后序列变成了 {1, 2} 和 {4, 5} 两段,不满足条件。而删除颜色 1 后序列变成了 {2, 3, 4, 5},满足条件。

    两个方案不同当且仅当至少存在一个颜色 i 只在其中一个方案中被删去。。

    Input Format

    第一行输入一个整数 T 表示数据组数。
    每组数据第一行输入一个整数 n 表示数列长度。
    第二行输入 n 个整数描述颜色序列。

    Output Format

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

    Sample Input

    1
    5
    1 3 2 4 3

    Sample Output

    6

    Hint

    【样例说明】
    满足条件的删颜色方案有 {1}, {1, 3}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, ∅.

     

    【数据规模与约定】

    对于 20% 的数据,保证 1 ≤∑n ≤ 20。

    对于 40% 的数据,保证 1 ≤∑n ≤ 500。

    对于 60% 的数据,保证 1 ≤∑n ≤ 10^4。

    对于 100% 的数据,保证 1 ≤ T,∑n ≤ 3 × 10^5, 1 ≤ Ai ≤ n。