题目描述

给定一个长度为 $N$ 的序列 $A=(A_1, A_2, \dots , A_N)$。你需要恰好执行一次如下操作：

选择一对整数 $(L,R)$，满足 $1 \leq L \leq R \leq N$，然后将区间 $A_L, A_{L+1}, \dots, A_R$ 中的所有元素替换为 $A_L$。

请问，执行该操作后，序列 $A$ 可能有多少种不同的结果？

输入格式

输入由标准输入给出，格式如下：

• 第一行一个正整数 $N$ 表示输入序列的长度；
• 第二行 $N$ 个由空格隔开的正整数，第 $i$ $(1 \le i \le N)$ 个正整数表示 $a_i$ 。

输出格式

输出一个整数，表示不同结果序列的数量。

样例输入 1

4
1 1 2 3

样例输出 1

4

样例输入 2

10
2 5 6 5 2 1 7 9 7 2

样例输出 2

41

说明

样例 1 解释

执行操作后可能得到的 $4$ 种序列如下：

• $(1,1,1,1)$
• $(1,1,1,3)$
• $(1,1,2,2)$
• $(1,1,2,3)$

例如，选择 $L=2, R=3$，即可得到 $(1,1,1,3)$。

数据范围

• 所有输入均为整数
• $1 \leq N \leq 10^6$
• $1 \leq A_i \leq N$