问题描述

你从你的邻居那里收到了一个钉着一排$n$个染了色的钉子的木板和两个完全相同的橡皮筋。第$i$个钉子的颜色是$a_i$。 对于每个橡皮筋，你需要找到两个颜色相同的钉子，将橡皮筋套在上面。我们称这个橡皮筋覆盖了这两个钉子之间的区间。

然而，邻居还提出了其他要求：这两个橡皮筋不能使用相同的钉子，并且两个橡皮筋覆盖的区间必须相交但不能包含。 举个例子，橡皮筋$1$套住了$[1,2]$，橡皮筋$2$套住了$[3,4]$，这两个区间相离，不满足要求； 橡皮筋$1$套住了区间$[1,3]$，橡皮筋$2$套住了区间$[2,4]$，两个区间相交，满足要求； 橡皮筋$1$套住了区间$[1,4]$，橡皮筋$2$套住了区间$[2,3]$，区间$1$包含区间$2$，不满足要求。

他要求你求不同的套橡皮筋的方案数。由于两个橡皮筋完全相同，两个方案不同当且仅当存在至少一个钉子在第一个方案中被选择而第二个方案中未被选择。

格式

输入格式

请从文件 quad.in 读入以下数据。

第一行，输入一个正整数$n$，表示钉子个数。 第二行，输入$n$个正整数，其中第$i$个正整数为$a_i$。表示钉子的颜色。

输出格式

请向文件 quad.out 写入以下数据。

第一行一个非负整数，表示方案数。

样例

6
1 3 3 1 2 3

2

5
2 2 2 2 2

5

数据规范

对于50%的数据，$1≤n≤10^2$

对于100%的数据，$1≤n≤5×10^3,1≤a_i≤n$