题目链接：http://acm.nbut.edu.cn/Contest/view/id/70/problem/B.xhtml

题意：给出n(n≤100000<script id="MathJax-Element-1" type="math/tex">n\leq 100000</script>)个正整数，考虑这个序列的连续的子序列的个数，将含有两个以上相同数字的子序列排除在外，将不同位置的相同序列算作两种，问这样的序列有多少个？为了便于描述，将这种序列称为W序列。

输入格式：每个样例首先输入正整数的个数n，然后是n个正整数，有多组样例

输出所求序列的个数

样例输入

5

3 4 5 5 2

3

1 2 3

样例输出

9 6

分析：

(1) 对于序列中的每个数a[i]，考虑以第 i 个数结尾的W序列的个数。如果记f(i)=max{k|a[k]==a[i],k=1,2,?,i?1}<script id="MathJax-Element-2" type="math/tex">f(i)=\max \{k|a[k]==a[i], k=1,2,\cdots,i-1\}</script>，那么以第 i 个数结尾的所有W序列的起始位置不小于f(i)<script id="MathJax-Element-3" type="math/tex">f(i)</script>。

(2) 根据这个性质，如果维护p=max{x|x=f(j),j=1,2,?,i}<script id="MathJax-Element-4" type="math/tex">\text{p}=\max\{x|x=f(j), j=1,2,\cdots,i\}</script>，那么就可以得到以第 i 个数结尾的所有W序列的个数为i-p+1，这样遍历所有的i=1...n，累加就是所求。

(3) 题目没有给出正整数a[i]的范围，需要离散化一下(O(nlog(n)<script id="MathJax-Element-5" type="math/tex">O(n\log(n)</script>))，总的复杂度O(n+nlog(n))<script id="MathJax-Element-6" type="math/tex">O(n+n\log(n))</script>。