103714: [Atcoder]ABC371 E - I Hate Sigma Problems

Problem Statement

You are given a sequence of integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$. Define $f(l, r)$ as:

• the number of distinct values in the subsequence $(A_l, A_{l+1}, \ldots, A_r)$.

Evaluate the following expression:

Constraints

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3
1 2 2

Sample Output 1

8

Consider $f(1,2)$. The subsequence $(A_1, A_2) = (1,2)$ contains $2$ distinct values, so $f(1,2)=2$.

Consider $f(2,3)$. The subsequence $(A_2, A_3) = (2,2)$ contains $1$ distinct value, so $f(2,3)=1$.

The sum of $f$ is $8$.

Sample Input 2

9
5 4 2 2 3 2 4 4 1

Sample Output 2

111

问题陈述

给定一个长度为N的整数序列A = (A_1, A_2, …, A_N)。
定义f(l, r)为：

• 子序列(A_l, A_{l+1}, …, A_r)中不同值的数量。

计算以下表达式的值：

约束条件

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq N$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$
$A_1$ $\ldots$ $A_N$

输出

打印答案。

示例输入1

3
1 2 2

示例输出1

8

考虑f(1,2)。子序列(A_1, A_2) = (1,2)包含2个不同的值，所以f(1,2)=2。

考虑f(2,3)。子序列(A_2, A_3) = (2,2)包含1个不同的值，所以f(2,3)=1。

f的和是8。

示例输入2

9
5 4 2 2 3 2 4 4 1

示例输出2

111