CF1004C Sonya and Robots

由于 Sonya 也对机器人感兴趣，她决定制造能够读取和识别数字的机器人。 Sonya 在一排中画了 $n$ 个数字，第 $i$ 个位置上是 $a_i$。她还在这排数字的两端各放置了一个机器人（分别在第一个数字的左侧和最后一个数字的右侧）。Sonya 会给每个机器人分配一个数字（可以相同也可以不同），然后让它们开始运行。当机器人运行时，它会朝另一个机器人移动，读取排中的数字。当机器人读取到与分配给它的数字相等的数字时，它就会关闭并停在当前位置。 Sonya 不希望机器人相遇，因此她会分配这样的数字，使得两个机器人会在相遇之前停下来。也就是说，她希望它们停在不同的位置，并且第一个机器人停在第二个机器人左侧。 例如，如果数字序列为 $[1, 5, 4, 1, 3]$，Sonya 给第一个机器人分配数字 $1$，给第二个机器人分配数字 $4$，那么第一个机器人会停在第 $1$ 个位置，第二个机器人会停在第 $3$ 个位置。这样，两个机器人不会相遇，因此不会损坏。但如果 Sonya 给第一个机器人分配数字 $4$，给第二个机器人分配数字 $5$，那么第一个机器人会停在第 $3$ 个位置，第二个机器人会停在第 $2$ 个位置，这样它们就会相遇。 Sonya 明白，给机器人分配一个在序列中没有出现过的数字是没有意义的，因为机器人永远找不到这个数字，最终会相遇。 现在 Sonya 想知道，有多少种不同的数字对可以分配给机器人，使得它们不会相遇。换句话说，她想知道有多少对 $(p, q)$，可以分别分配给第一个和第二个机器人。只要 $p_i \neq p_j$ 或 $q_i \neq q_j$，则 $(p_i, q_i)$ 和 $(p_j, q_j)$ 被认为是不同的。 不幸的是，Sonya 正忙于修理因失败而损坏的机器人。因此，她请你帮忙计算有多少种分配方式可以让机器人不相遇。

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

输出一个整数，表示 Sonya 可以分配给机器人且不会相遇的不同数字对的数量。

在第一个样例中，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)$。 由 ChatGPT 4.1 翻译