由于索尼娅也对机器人技术感兴趣,她决定建造能够读取和识别数字的机器人。
Sonya 连续抽取了 $$$n$$$ 个数字,$$$a_i$$$ 位于第 $$$i$$$ 个位置。她还在该行的每一端放置了一个机器人(第一个数字的左侧和最后一个数字的右侧)。索尼娅会给每个机器人一个编号(它们可以相同或不同)并运行它们。当一个机器人运行时,它会向另一个机器人移动,读取该行中的数字。当机器人读取的数字等于给予该机器人的数字时,它将关闭并保持在相同的位置。
索尼娅不希望机器人坏掉,所以她会给出这样的数字,让机器人在相遇之前停下来。也就是说,女孩希望他们停在不同的位置,以便第一个机器人位于第二个机器人的左侧。
例如,如果写入数字 $$$[1, 5, 4, 1, 3]$$$,Sonya 将数字 $$$1$$$ 给第一个机器人,将数字 $$$4$$$ 给第二个机器人,第一个机器人将停在 $$$1$$$-st 位置,而第二个机器人将停在 $$$3$$$-rd 位置。 In that case, robots will not meet each other. As a result, robots will not be broken.但是,如果索尼娅将数字 $$$4$$$ 给第一个机器人,将数字 $$$5$$$ 给第二个机器人,那么它们就会相遇,因为第一个机器人将停在 $$$3$$$-rd 位置,而第二个机器人将停在 $$$2$$$-nd 位置。
Sonya 明白,给出未写在该行中的数字是没有意义的,因为机器人不会找到该数字,并且会遇到另一个机器人。
索尼娅现在有兴趣找到她可以给机器人的不同配对的数量,这样它们就不会相遇。换句话说,她想知道对的数量($$$p$$$,$$$q$$$),其中她将 $$$p$$$ 给第一个机器人,将 $$$q$$$ 给第二个机器人。如果 $$$p_i\neq p_j$$$ 或 $$$q_i\neq q_j$$$,则对 ($$$p_i$$$, $$$q_i$$$) 和 ($$$p_j$$$, $$$q_j$$$) 不同。
不幸的是,索尼娅正忙于修复发射失败后损坏的机器人。这就是为什么她要求你找出她可以给机器人的配对数量,这样它们就不会相遇。
输入
第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^5$$$) — 一行中的数字数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^5$$$) — 一行中的数字。
输出
打印一个数字——索尼娅可以给机器人的可能配对数量,这样它们就不会相遇。
示例
输入 #1
5 1 5 4 1 3
输出 #1
9
输入 #2
7 1 2 1 1 1 3 2
输出 #2
7
注意
在第一个例子中,Sonya 可以给出对 ($$$1$$$, $$$1$$$), ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$1$$$, $$$5$$$), ($$$4$$$, $$$1$$$), ($$$4$$$、$$$3$$$)、($$$5$$$、$$$1$$$)、($$$5$$$、$$$3$$$) 和 ($$$5$$$、$$$4$$$)。
在第二个例子中,Sonya 可以给出对 ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), ($$$2$$$, $$$1$$$), ($$$2$$$, $$$2$$$), ($$$2$$$、$$$3$$$)和($$$3$$$、$$$2$$$)。