English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.
[samples]
## Note
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$).
由于索尼娅对机器人也感兴趣，她决定建造能够读取并识别数字的机器人。
索尼娅在一行中画了 $n$ 个数字，第 $i$ 个位置是 $a_i$。她还在行的两端各放置了一个机器人（第一个数字的左侧和最后一个数字的右侧）。索尼娅会给每个机器人分配一个数字（可以相同也可以不同），然后启动它们。当机器人运行时，它会朝着另一个机器人移动，并读取行中的数字。当机器人读到一个与分配给它的数字相等的数时，它会关闭并停留在该位置。
索尼娅不希望机器人损坏，因此她会分配这样的数字，使得机器人在相遇前停止。也就是说，她希望它们停在不同的位置，使得第一个机器人位于第二个机器人的左侧。
例如，如果写下的数字是 $[1, 5, 4, 1, 3]$，索尼娅给第一个机器人分配数字 $1$，给第二个机器人分配数字 $4$，那么第一个机器人将在第 $1$ 个位置停止，第二个机器人将在第 $3$ 个位置停止。在这种情况下，机器人不会相遇，因此不会损坏。但如果索尼娅给第一个机器人分配数字 $4$，给第二个机器人分配数字 $5$，它们就会相遇，因为第一个机器人会在第 $3$ 个位置停止，而第二个机器人会在第 $2$ 个位置停止。
索尼娅明白，分配一个不在行中出现的数字是没有意义的，因为机器人将找不到这个数字，从而与另一个机器人相遇。
索尼娅现在想知道，她可以给机器人分配多少对不同的数字，使得它们不会相遇。换句话说，她想知道有多少对 $(p, q)$，其中她将 $p$ 分配给第一个机器人，$q$ 分配给第二个机器人。如果 $p_i \ne p_j$ 或 $q_i \ne q_j$，则对 $(p_i, q_i)$ 和 $(p_j, q_j)$ 被认为是不同的。
不幸的是，索尼娅正忙于修复在失败发射后损坏的机器人。因此，她请你找出她可以分配给机器人且不会导致它们相遇的配对数量。
第一行包含一个整数 $n$（$1 \le n \le 10^5$）——行中数字的个数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）——行中的数字。
输出一个数——索尼娅可以分配给机器人且使它们不会相遇的可能配对数量。
在第一个例子中，索尼娅可以分配的配对有：$(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)$。
## Input
第一行包含一个整数 $n$（$1 \le n \le 10^5$）——行中数字的个数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）——行中的数字。
## Output
输出一个数——索尼娅可以分配给机器人且使它们不会相遇的可能配对数量。
[samples]
## Note
在第一个例子中，索尼娅可以分配的配对有：$(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)$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the sequence.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, n\} $.
Let $ S = \{ a_i \mid i \in \{1, \dots, n\} \} $ be the set of distinct values in $ A $.
For each value $ x \in S $, define:
- $ \text{left}(x) = \min \{ i \in \{1, \dots, n\} \mid a_i = x \} $, the leftmost occurrence of $ x $.
- $ \text{right}(x) = \max \{ i \in \{1, \dots, n\} \mid a_i = x \} $, the rightmost occurrence of $ x $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le a_i \le 10^5 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of ordered pairs $ (p, q) \in S \times S $ such that:
$$
\text{left}(p) < \text{right}(q)
$$
API Response (JSON)
{
"problem": {
"name": "C. Sonya and Robots",
"description": {
"content": "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 al",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1004C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.\n\nSonya has drawn $n$ numbers in a row, $a_i$ is located in the $i$\\-th position. She al...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "由于索尼娅对机器人也感兴趣，她决定建造能够读取并识别数字的机器人。\n\n索尼娅在一行中画了 $n$ 个数字，第 $i$ 个位置是 $a_i$。她还在行的两端各放置了一个机器人（第一个数字的左侧和最后一个数字的右侧）。索尼娅会给每个机器人分配一个数字（可以相同也可以不同），然后启动它们。当机器人运行时，它会朝着另一个机器人移动，并读取行中的数字。当机器人读到一个与分配给它的数字相等的数时，它会关闭并停...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z}^+ $ for all $ i \\in \\{1, \\dots, n...",
"is_translate": false,
"language": "Formal"
}
]
}