当前没有测试数据。

题目描述

在一年一度的校园科技节中，学校决定选拔一支机器人代表队参加全国青少年机器人创新大赛。共有 $N$ 位同学的机器人参与选拔，它们排成一行，第 $i$ 台机器人的型号为 $X_i$。代表队将从这 $N$ 位同学的机器人中进行选拔。

选拔标准如下：

• 从这一排机器人中，选出一个连续的区间，区间中的机器人将入选全国青少年机器人创新大赛。
• 连续的区间中，至少包含 $2$ 台机器人。
• 区间两端的机器人的型号和区间中其他机器人的型号必须不同，两端机器人的型号也要不同。形式化的讲，即：对于连续的区间 $[L, R]$，需满足 $X_L \neq X_R$，且对于区间中，位于位置 $i$ 上的机器人（$L < i < R$）需满足 $X_i \neq X_L$ 且 $X_i \neq X_R$。

请帮助学校计算出可以选派参加全国机器人创新大赛代表队的方法数。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $X_1, X_2, …, X_N$。

输出格式

输出一个整数，表示可能的代表队的数量。

样例 #1

输入

6
2 6 2 5 5 6

输出

6

数据范围

对于 $15\%$ 的数据，满足 $1 \le N \le 100$。

对于 $45\%$ 的数据，满足 $1 \le N \le 5000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 2 \times 10^5$，$1 \le X_i \le N$。