题目描述

齐鲁工带ACM集训队里面有很多大佬，比如：王翔，刘凡 等等 , 各自都身怀绝技,敲代码速度惊为天人，最近$Mr.$鹿给大家布置了很多题，但由于大佬们的好胜心过强，都想做难度最大的 ，为了公平，老师随机摇到旭宝来完成难度最大的题：找到不同对的 $i ，j$，使，其中不同对 $i ， j$ 的定义：1. $i~\\leq~j~\\leq~n-1$ 。2.所有的 $i ,j$ 对中无法出现任意两对存在 $i_1 = i_2$ 且 $j_1 =j_2$ 的情况。

集训队的大佬们都知道旭宝贼笨，都想帮旭宝秒了这道题。

身为大佬的你，请你来帮旭宝算一下，序列中有多少对不同的 $i，j$ 使得以上式子成立。

输入格式

第 $1$ 行输入 $n$ ($1~\\leq~n~\\leq~5*10^5$ ), $n$ 为给定序列中有多少个数

第 $2$ 行输入给定序列从左到右的元素 $a_i$ ($-10^9~\\leq~a_i~\\leq~10^9$ ) 。

输出格式

输出 $i，j$ 的符合题干所给条件的对数。

样例

5 
1 2 3 0 3

2

4 
0 1 -1 0

1

2 
4 1

0

提示

对于样例 $1$ ： 第一次可以将序列分为{$1$，$2$}，{$3$，$0$}，{$3$}，每个区间的和为 $3$ 。第二次可以将序列分为 {$1$，$2$}，{$3$}，{$0$，$3$}，每个区间的和为3.总共可以分为符合所给条件的不同两次，所以输出$2$.