United Cows of Farmer John

题目描述

Farmer John 的联合奶牛国（UCFJ）正在向国际牛类奥林匹克竞赛（IOI）派出代表团。 有 $N$ 头奶牛参与代表团的选拔（$1 \leq N \leq 2 \cdot 10^5$）。它们站成一排，第 $i$ 头奶牛的品种为 $b_i$。 代表团将由一个长度至少为 2 的连续区间组成——即对满足 $1\le l<r\le N$ 的整数 $l$ 和 $r$，选择奶牛 $l\ldots r$。所选区间最外侧的两头奶牛将被指定为“领袖”。为避免同品种冲突，每个领袖的品种必须与代表团中其余所有奶牛（无论是否为领袖）的品种都不同。 请帮助 UCFJ 确定（出于税务原因）他们选择代表团并派往 IOI 的方案数。

输入格式

第一行包含 $N$。 第二行包含 $N$ 个整数 $b_1,b_2,\ldots,b_N$，每个都在范围 $[1,N]$ 内。

输出格式

输出所有可能代表团的数量，占一行。 注意：本题中涉及的整数可能很大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。

7
1 2 3 4 3 2 5

13

提示

每个代表团都对应于下面这些领袖对之一：

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

SCORING: 测试点 1-3 满足 $N\le 100$。 测试点 4-8 满足 $N\le 5000$。 测试点 9-20 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold