CF1004C.Sonya and Robots

Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.

Sonya has drawn $n$ numbers in a row, $a_i$ is located in the $i$-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last number). Sonya will give a number to each robot (they can be either same or different) and run them. When a robot is running, it is moving toward to another robot, reading numbers in the row. When a robot is reading a number that is equal to the number that was given to that robot, it will turn off and stay in the same position.

Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.

For example, if the numbers $[1, 5, 4, 1, 3]$ are written, and Sonya gives the number $1$ to the first robot and the number $4$ to the second one, the first robot will stop in the $1$-st position while the second one in the $3$-rd position. In that case, robots will not meet each other. As a result, robots will not be broken. But if Sonya gives the number $4$ to the first robot and the number $5$ to the second one, they will meet since the first robot will stop in the $3$-rd position while the second one is in the $2$-nd position.

Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.

Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs ($p$, $q$), where she will give $p$ to the first robot and $q$ to the second one. Pairs ($p_i$, $q_i$) and ($p_j$, $q_j$) are different if $p_i\neq p_j$ or $q_i\neq q_j$.

Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.

由于索尼娅对机器人技术也很感兴趣，她决定制造能够读取和识别数字的机器人。

索尼娅将 $n$ 个数字排成一行，第 $i$ 个位置上的数字为 $a_i$。她还在该行两端（即第一个数字的左侧与最后一个数字的右侧）各放置了一个机器人。索尼娅将为每个机器人分配一个数字（这两个数字可以相同，也可以不同），然后启动它们。当机器人运行时，它会朝另一个机器人方向移动，并依次读取该行中的数字。当机器人读取到一个与其被分配的数字相等的数字时，它便会立即关闭并停留在当前位置。

索尼娅不希望机器人发生碰撞，因此她只会分配满足如下条件的数字：两个机器人在相遇前就已停止。换言之，她希望两个机器人最终停在不同的位置上，且第一个机器人（位于左侧）停在第二个机器人（位于右侧）的左侧。

例如，若写下的数字为 $[1, 5, 4, 1, 3]$，索尼娅给第一个机器人分配数字 $1$、给第二个机器人分配数字 $4$，则第一个机器人将在第 $1$ 个位置停止，而第二个机器人将在第 $3$ 个位置停止。此时，两个机器人不会相遇，因而不会损坏。但若索尼娅给第一个机器人分配数字 $4$、给第二个机器人分配数字 $5$，则它们将会相遇：因为第一个机器人将在第 $3$ 个位置停止，而第二个机器人将在第 $2$ 个位置停止（注意：第二个机器人从右端向左移动，遇到的第一个等于 $5$ 的数字位于原数组索引 $2$ 处，即从左往右数第 $2$ 个位置）。

索尼娅意识到，给机器人分配一个未出现在该行中的数字是没有意义的，因为该机器人将无法找到该数字，从而一直移动直至与另一机器人相遇。

目前，索尼娅正忙于修理因一次失败启动而损坏的机器人，因此她想请你帮忙计算：有多少种不同的数字对 $(p, q)$ 可以分配给两个机器人，使得它们不会相遇？换句话说，她想知道满足条件的有序对 $(p, q)$ 的个数，其中 $p$ 分配给第一个机器人，$q$ 分配给第二个机器人。若 $(p_i, q_i)$ 与 $(p_j, q_j)$ 满足 $p_i \ne p_j$ 或 $q_i \ne q_j$，则认为它们是不同的对。

The first line contains a single integer $n$ ($1\leq n\leq 10^5$) — the number of numbers in a row.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10^5$) — the numbers in a row.

第一行包含一个整数 $n$（$1\leq n\leq 10^5$）—— 表示一行中数字的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\leq a_i\leq 10^5$）—— 表示一行中的数字。

Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.

输出一个数字——Sonya 可以给机器人分配的、使得它们不会相遇的可能配对数量。

In the first example, Sonya can give pairs ($1$, $1$), ($1$, $3$), ($1$, $4$), ($1$, $5$), ($4$, $1$), ($4$, $3$), ($5$, $1$), ($5$, $3$), and ($5$, $4$).

In the second example, Sonya can give pairs ($1$, $1$), ($1$, $2$), ($1$, $3$), ($2$, $1$), ($2$, $2$), ($2$, $3$), and ($3$, $2$).

在第一个例子中，索尼娅可以给出如下数对：$(1, 1)$、$(1, 3)$、$(1, 4)$、$(1, 5)$、$(4, 1)$、$(4, 3)$、$(5, 1)$、$(5, 3)$ 和 $(5, 4)$。

在第二个例子中，索尼娅可以给出如下数对：$(1, 1)$、$(1, 2)$、$(1, 3)$、$(2, 1)$、$(2, 2)$、$(2, 3)$ 和 $(3, 2)$。