题目背景

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

1000 190 505
497 451 1538 787 1452 696 1451 597 343 1960 453 1016 1179 755 1100 24 1502 1588 1691 543 1795 602 337 1275 760 1886 435 565 306 1396 629 335 1290 1416 678 1654 1888 1056 859 155 1614 1179 598 1756 1509 1327 1948 1497 523 1790 24 137 1858 1510 233 98 1901 1624 1200 951 629 1710 1072 1894 544 1039 610 134 1075 196 172 1495 1312 1741 276 347 198 1172 1873 1863 402 1389 80 1616 564 1349 437 1489 719 253 661 1295 1294 522 52 1097 1311 1330 357 860 927 1143 1566 84 542 1194 1394 1837 1244 989 505 802 1912 1809 1438 307 1539 1509 1789 20 700 243 1047 1991 42 1499 1946 395 571 477 1961 1910 673 168 761 1681 1530 1441 1348 1206 64 1465 1762 2 1930 629 1998 280 882 1948 1453 569 1842 440 554 959 1503 189 1560 1544 439 1929 1446 939 75 545 325 430 1830 1347 795 242 1787 464 1709 1948 1810 285 1019 361 282 842 445 453 1060 507 1116 565 1234 881 96 482 30 957 753 1020 1651 286 1241 1900 247 1807 1286 937 323 943 1845 481 1186 517 205 1403 1510 1121 1109 1424 1262 1251 1836 1779 325 304 1063 1323 1841 414 740 119 1330 1934 462 428 1484 467 1380 1072 1174 574 1066 1556 561 247 1388 1781 364 1435 1801 1571 1997 535 128 1356 1777 1522 1278 481 490 429 444 1115 989 309 1369 929 113 714 516 1414 1644 560 1913 1371 1758 1892 1731 1313 22 1095 50 178 513 472 458 866 1093 1011 899 966 1351 607 54 1975 1071 60 491 1114 1103 608 1989 221 1535 1883 20 1905 603 17 128 575 561 382 1655 461 1432 1675 517 1900 1374 982 83 1938 950 964 1379 1162 640 1517 1105 1342 202 1163 52 1363 902 89 883 903 1436 277 1865 253 1463 190 493 1433 586 846 1103 947 559 565 796 1033 1497 488 817 926 1753 308 1590 531 693 1699 603 133 337 1584 907 1194 1384 862 80 147 771 1997 1459 1766 1685 154 1682 393 24 723 1158 581 1902 457 1114 393 1964 159 121 541 452 366 1268 1194 1977 554 385 763 524 529 1882 283 1778 974 101 1798 963 722 158 1632 1341 1749 204 701 1035 1558 1790 478 1100 1245 923 814 265 1379 219 1223 583 1924 648 568 721 1934 1012 1985 753 100 412 1673 1383 1508 461 595 1764 1005 970 1834 824 665 727 559 333 149 457 79 1883 1314 23 389 1070 1641 230 1921 1327 358 1558 1922 696 261 550 837 1120 739 1663 878 1305 1884 963 511 373 1608 1156 1724 301 641 1606 1840 69 956 1092 981 678 604 204 175 785 524 590 800 1828 936 1503 1699 132 587 1800 1859 1643 288 744 934 1346 1564 1399 1364 1051 1570 1241 857 866 1131 499 64 372 1523 414 255 789 1361 726 1288 1853 1206 1490 1433 1378 1315 826 589 1571 795 357 867 488 1583 1969 271 1899 1939 473 1231 1641 1582 631 1904 1800 1192 1882 291 1982 517 497 1420 377 909 950 781 1895 327 39 922 704 1295 1601 399 1783 1159 918 306 1668 617 1134 1419 651 1795 693 1794 332 1201 911 589 1389 1824 60 1577 672 1467 375 398 1004 1931 80 419 1885 154 1720 682 304 52 1822 1165 942 1094 1426 1353 1857 104 776 1549 483 830 476 877 410 1630 317 1663 885 312 162 738 1557 20 1830 1655 185 1283 1972 50 83 7 172 1633 260 1628 1308 257 1180 197 1607 779 1 956 1154 1430 201 304 343 1507 1585 121 1505 495 1447 985 697 261 1891 153 1715 607 1193 1304 1455 1095 1588 1379 1907 674 1330 1859 1287 1594 278 687 1015 579 1523 1961 1742 12 1710 990 1058 772 1719 842 1407 945 1173 1330 1197 707 712 633 187 1281 1013 481 472 1959 614 320 867 1276 1638 1324 155 921 675 1123 679 1545 727 829 1727 1160 1843 1450 1590 851 173 67 1392 291 1562 448 150 1743 554 406 744 1439 1994 534 420 1937 1811 455 896 1065 1032 544 189 905 984 1056 362 398 160 1626 305 855 1622 1691 1499 1596 230 657 519 1464 350 487 1609 421 1242 1868 631 1459 1483 333 1545 1022 1083 817 1087 1711 1728 897 1274 411 745 1394 1792 1457 258 1880 927 947 1420 1206 92 837 395 132 657 1263 1612 473 10 592 1121 649 1023 819 1168 278 569 1504 754 220 465 1488 1594 67 302 1419 1708 1320 199 1062 1022 572 288 1921 1681 572 1988 583 689 727 847 153 1010 1896 1795 1251 1674 618 1557 1959 941 345 504 142 1876 930 1847 831 158 1409 611 1626 1595 1486 721 1665 1613 1791 1633 1868 313 761 1527 358 457 1554 1111 594 1764 1771 983 1003 1612 636 1794 1064 525 688 1623 921 1429 180 1502 1266 169 1474 23 236 1690 585 637 168 175 1131 573 244 446 590 1888 1977 1758 1516 1102 435 998 136 688 569 720 1671 988 1931 848 1152 3 1930 780 1989 435 833 1857 1535 942 135 1827 211 1484 183 1621 45 1311 442 1926 1246 978 350 1481 705 612 5 1234 1285 1823 1463 625 553 1375 1442 1080 1306 577 1722 500 508 1641 1052 717 750 1981 1087 1547 1422 549 499 1542 1839 1340 1094 1484 947 1885 940 1526 624 691 609 657 318 1987 1121 23 675 114 1872 1504 263 1953 1928

318

样例 3

见附加文件中的 [gedit3.in](file:gedit3.in) 与 [gedit3.ans](file:gedit3.ans)。

这组样例满足子任务 4 的数据规模和特殊性质。

数据范围与提示

对于 $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$ 各不相同。