[R79F]展品 - 代码源竞赛平台

时空限制

1S/512M

题目描述

展厅按顺序摆放了 $n$ 件展品，第 $i$ 件展品的类别编号为 $a_i$。工作人员想从中选取一段连续的展品，制作一份展签。

如果在非空区间 $[L,R]$ 中，不存在四个下标 $i,j,k,l$ 满足

$$L\le i<j<k<l\le R,\qquad a_i=a_k,a_j=a_l,\qquad a_i\ne a_j$$

就称这段展品的区间合法。

也就是说，区间内不能选出两个不同的类别，使它们按 $x,y,x,y$ 的顺序出现。选出的四个位置可以不相邻。同一个类别出现四次或更多次是允许的。

请计算合法非空区间的数量。左右端点不同的区间分别计数，即使其中的类别序列相同。

格式

输入格式

第一行包含一个正整数 $n$，为展品的数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 为第 $i$ 件展品的类别编号。

输出格式

• 输出一个正整数，表示合法非空区间的数量。

样例

样例输入 #1

4
1 2 1 2

样例输出 #1

9

样例解释 #1

十个非空区间中，只有整个区间 $[1,4]$ 不合法。

样例输入 #2

4
1 1 1 1

样例输出 #2

10

样例解释 #2

所有展品的类别相同，全部区间合法。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$80$	无
$2$	$20$	$2\times10^5$	A
$3$	$50$		无

特殊性质 A：$a_1,a_2,\ldots,a_n$ 是 $1,2,\ldots,n$ 的一个排列。

对于 $100\%$ 的数据，满足 $1\le n\le2\times10^5$，$1\le a_i\le n$。输入中的所有数均为整数。