题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。

有多少种方案可以从中选取一个连续子段，使该子段内所有元素的值都相同？

输入格式

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

第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示满足要求的连续子段数量。

输入输出样例

输入 #1

5
3 1 1 2 5

输出 #1

6

说明/提示

每个元素单独成段均满足要求，共有 $\{3\}$、$\{1\}$、$\{1\}$、$\{2\}$、$\{5\}$ 这 $5$ 种方案；第 $2$、$3$ 个元素组成的子段 $\{1,1\}$ 也满足要求，因此共有 $6$ 种方案。

数据范围

• 对于 $60\%$ 的数据，$1\le n\le 10^3$；
• 对于 $80\%$ 的数据，$1\le n\le 10^5$；
• 对于全部数据，$1\le n\le 10^6$，$-10^9\le a_i\le 10^9$。

5
3 1 1 2 5

6

33
16 1 16 -15 13 -7 -10 1 13 -19 -1 7 -5 7 7 -20 20 1 -12 12 -20 -18 -11 -12 0 -6 9 -5 -7 -8 -14 15 -14

34

61
-17 1 17 10 15 -10 10 3 17 2 1 -15 13 16 -13 13 14 1 -17 -5 -3 20 -3 5 7 4 -12 1 -19 10 -3 -19 -7 8 9 -17 -9 -18 17 9 -4 1 17 -10 -4 3 -16 8 20 -1 10 13 -3 6 -17 8 -11 2 4 8 -2

61