题目背景

CTT2021 D1T3

题目描述

人类目前已经研究出了多种基因编辑技术，其中最传统的一种技术需要用到“限制性核酸内切酶”（简称限制酶）。这种酶能够识别特定的核苷酸序列，并在指定的位点上切割连接相邻核苷酸的磷酸二酯键，产生被称为“末端”的序列切口。只有相匹配的末端才能用 DNA 连接酶进行连接。

假设现在要用基因片段 $A$ 去替换某一载体 $V$ 上的基因片段 $B$。在使用限制酶的编辑技术中，通常需要进行以下操作：

1. 在基因 $A$ 的两端各选择一种限制酶识别位点。这两处识别位点在基因 $B$ 的两端也应当相应存在。
2. 用所选择的识别位点对应的限制酶对基因 $A$ 进行处理，使得其两端产生相应的末端。将处理后的基因 $A$ 提纯。
3. 用同样的限制酶切断载体 $V$ 上的识别位点，使得基因 $B$ 与载体 $V$ 断开。纯化出去除了基因 $B$ 的载体 $V'$。
4. 将载体 $V'$ 与基因 $A$ 混合，并在 DNA 连接酶的帮助下将断开的磷酸二酯键重新接上。

值得一提的是，如果两处识别位点断开后产生了相同的末端，那么在第 4 步中载体 $V'$ 有可能单独连接起来，产生了不包含基因 $A$ 或 $B$ 的载体；也有可能基因 $A$ 反向接入 $V'$，同样产生错误的载体。因此，在实际运用中，通常选取产生不同末端的限制酶对基因 $A$ 和载体 $V$ 进行处理。

公元 3032 年，人类发现了一种掌握了基因编辑技术的外星文明 HD1048576d。当然，这种基因编辑的技术仅限于居住在 HD1048576d 这颗行星上的外星生物的基因。我们人类掌握的基因编辑技术可识别的最小单位是 DNA 序列上的单个碱基，而外星文明的基因编辑技术可识别的最小单位是其基因序列上的单个 noicleobase。出于方便起见，我们可以将单个 noicleobase 用从 $1$ 开始的正整数表示，那么一段外星生命的基因序列就可以被表示成相应的正整数序列。

对于一段长度为 $n$ 的外星生命的基因序列（不妨记其正整数表示为 $s_1, s_2, \cdots, s_n$），外星文明 HD1048576d 的基因编辑过程如下：

1. 选择一段要编辑的区域 $[l, r]$，即原位替换原序列中 $s_l, s_{l+1}, \cdots, s_r$ 这部分子序列；
2. 挑选一对跨过待替换区域的下标 $(i, j)$（即 $1\le i<l$ 且 $r<j\le n$），批量生产出 $s_i, \cdots, s_j$ 这段子序列在编辑后对应的新序列 $s_i, \cdots, s_{l-1}, t_1, \cdots, t_k, s_{r+1}, \cdots, s_j$；
3. 通过对应的特异性识别工具，将 $s_i, \cdots, s_j$ 这段子序列从原序列中断开，并将 $s_i, \cdots, s_{l-1}, t_1, \cdots, t_k, s_{r+1}, \cdots, s_j$ 接到序列中，即可得到目标基因序列。

需要注意的是，在步骤 2 中，挑选的这对下标必须对应唯一的 noicleobase 组合。也就是说，能够满足 $s_{i'}=s_i, s_{j'} = s_j$ 且 $i<j$ 的有序对 $\left(i', j'\right)$ 必须是唯一的（即为 $(i, j)$），否则特异性识别工具可能切割下其它区段的基因序列；另外，$s_i\ne s_j$，否则特异性识别工具可能只切割下单个 noicleobase。

另外，由于替换时需要生产新的基因序列，而生产这样的序列需要不小的开销，所以外星文明希望能够最小化需要生产的基因序列长度。显然，最小化这一长度等价于最小化被切割下来的基因子序列的长度，所以实践中一般是通过最小化被切割下来的基因子序列长度来计算最优解的。

现在，他们想考考人类文明的智力水平，于是你被他们从众多高中生中挑选出来解决这一问题。

输入格式

输入的第一行包含三个正整数 $n, l, r$，表示待编辑的基因序列的长度，需要编辑的区域的左端点，和需要编辑的区域的右端点。保证 $3\le n\le 10^6$ 且 $1<l\le r < n$。

输入的第二行包含 $n$ 个正整数 $s_1, \cdots, s_n$，表示用正整数表示的待编辑的基因序列。保证每个 noicleobase 的编号 $s_i$ 都在 $[1, 10^6]$ 中。

输出格式

如果存在满足外星文明的基因编辑技术限制的基因序列切割方案，则输出一个正整数，表示输出所有方案中，被切割下来的基因子序列的最小值。否则，输出 -1，表示不存在满足限制的切割方案。

10 4 6
2 1 4 7 4 8 3 6 4 8

6

提示

最优方案为切割 1 4 7 4 8 3。可以证明，没有比这更优秀的满足技术限制的切割方案。

一种比该方案切割长度更短的方案是 4 7 4 8 3，但是在这种方案中特异性识别工具可能会断开 4 8 3，从而导致产生的目标基因序列出现意外的突变，因此这种切割方案不满足技术限制。

对于 $100\%$ 的数据，保证 $3\le n \le 10^6$，$\forall 1\le i\le n, 1\le s_i\le 10^6$，且 $1<l\le r<n$。

本题共有 5 个子任务，你需要通过一个子任务中的所有测试点才能获得该子任务的相应分数。下表为各子任务的数据规模及性质。

上表中的“特殊性质”为：$s_1, \cdots, s_{l - 1}$ 各不相同，且 $s_{r + 1}, \cdots, s_n$ 各不相同。