题面 样例

题目描述

给出长度为 $n$ 的序列 $a_i$ 满足 $1\le a_i\le n$，且每个 $a_i$ 至多出现两次。定义可重集 $S(l,r)=\{a_l,a_{l+1},...,a_r\}$。现在求：

即本质不同的 $S(l,r)$ 数量。

输入格式

从 ds.in 中读入。

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$。

输出格式

输出到 ds.out 中。

输出本质不同的 $S(l,r)$ 数量。

样例输入 1

5
1 2 3 1 3

样例输出 1

11

数据范围

对于所有数据，保证 $n\le 5\times 10^5$。

对于测试点 $1\sim 2$，满足 $n\le 100$。

对于测试点 $3\sim 5$，满足 $n\le 2000$。

对于测试点 $6\sim 7$，满足 $n=2m$，且 $a_1\sim a_{m}$ 互不相同，$a_{m+1}\sim a_{2m}$ 也互不相同。

对于测试点 $8\sim 10$，无特殊约束。