瓦莱里对魔法非常感兴趣。魔法如此吸引他,以至于他到处都能看到它。他通过超自然力量的介入来解释任何奇怪、怪异的现象。但谁会想到,即使在规则的数字数组中,瓦莱拉也能看到一些美丽而神奇的东西。
瓦莱拉绝对无意中得到了一张古老的羊皮纸,上面写着一系列数字。他立刻想到这个数组中的数字并不是随机的。经过广泛的研究,瓦莱拉得出了魔法数组应该具有的一个奇妙的特性:如果数组的最小值和最大值一致,则该数组被定义为魔法。
他决定与您分享这一杰出的发现,但他要求您提供帮助作为回报。尽管瓦莱拉拥有巨大的智慧和智慧,但他的价值却非常低,所以你必须完成他的工作。您所要做的就是计算写在羊皮纸上的原始数字数组的神奇子数组的数量。子数组被定义为连续元素的非空序列。
输入
输入数据的第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含原始整数数组 a1, a2, ..., an (- 109 ≤ ai ≤ 109)。
输出
在单行上打印问题的答案:子数组的数量,这很神奇。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位数字。建议使用 cin、cout 流(也可以使用 %I64d 指定符)。
示例
输入 #1
4 2 1 1 4
输出 #1
5
输入 #2
5 -2 -2 -2 0 1
输出 #2
8
注意
样本测试注意事项:
神奇的子数组显示为带有开头和结尾的索引对 [a;b]。
在第一个示例中:[1;1]、[2;2]、[3;3]、[4;4]、[2;3]。
在第二个示例中:[1;1]、[2;2]、[3;3]、[4;4]、[5;5]、[1;2]、[2;3]、[1;3]。