Description

今年的 EGOI 在波恩举办。主办方希望为比赛中的每支队伍最多分发一个礼品盒，每支队伍的编号为 $0$ 到 $T-1$。所有参赛选手排成一排，但他们的顺序是混乱的，因此同一队的成员可能不会站在一起。注意，队伍中一定至少有一支队伍在队列中有多于一名成员。队列中共有 $N$ 个人，第 $i$ 个人属于编号为 $a_i$ 的队伍。问题是：每支队伍最多只能获得一个礼品盒。为了让礼品发放过程顺利进行——即使因此有些队伍无法获得礼品盒——主办方希望在发放过程中恰好暂停一次，跳过一段连续的选手，然后再继续发放。换句话说，他们会跳过一个连续区间 $[\ell, r]$ 的选手。

并不要求每支队伍都必须收到礼品盒。然而，主办方希望在不违反“每支队伍至多一个礼品盒”这一前提下，使收到礼品盒的队伍数尽量多，同时要最小化被跳过的选手数量。请帮助主办方决定在哪一段暂停以及何时继续发放礼品盒，才能使被跳过的选手尽可能少。

Input Format

输入的第一行包含两个整数 $T$ 和 $N$——队伍数和队列中的选手数。

第二行包含 $N$ 个整数 $a_i$，第 $i$ 个整数表示队列中第 $i$ 个选手所属的队伍编号。保证 $0$ 到 $T-1$ 的每个整数至少出现一次。

Output Format

输出两个整数 $\ell$ 和 $r$，分别表示被跳过的第一个和最后一个选手的下标。注意，$\ell$ 和 $r$ 的下标范围为 $0$ 到 $N-1$。如果有多个解，输出其中任意一个即可。

4 5
1 3 0 2 3

1 1

3 6
1 0 2 2 1 0

0 2

4 8
0 2 0 1 2 1 3 3

2 6

3 6
1 1 2 0 1 0

0 3

4 6
0 1 2 0 3 2

2 3

5 13
3 3 3 1 2 0 3 3 2 1 4 1 0

1 9

Hint

第一个样例满足测试组 1、3、5 和 6 的约束。有两种不同的输出：$1\ 1$（对应下划线蓝色线段）和 $4\ 4$（对应红色虚线），如图所示。无论哪种方式，四支队伍都能收到礼品盒，且没有队伍收到多于一个礼品盒。

$\begin{array}{lllll} 1 & \blue 3 & 0 & 2 & \red 3 \end{array}$

第二个样例满足测试组 2、3、4、5 和 6 的约束。同样有两种不同的输出：$0\ 2$ 和 $3\ 5$，如图所示。两种方案下，三支队伍都能收到礼品盒。

$\begin{array}{lllll} \blue 1 & \blue 0 & \blue 2 & \red 2 & \red 1 & \red 0 \end{array}$

第三个样例满足测试组 3、4、5、6 的约束。最优解是三支队伍收到礼品盒，如下所示。下标为 0、1、7 的选手（分别属于队伍 0、2、3）收到礼品盒。这是唯一的可行解。

$\begin{array}{lllllll} 0 & 2 & \blue 0 & \blue 1 & \blue 2 & \blue 1 & \blue 3 & 3 \end{array}$

第四个样例满足测试组 3、5 和 6 的约束。同样有两种不同的输出：$0\ 3$ 和 $1\ 4$，如图所示。两种方案下，恰好两支队伍（队伍 0 和队伍 1）获得礼品盒。队伍 2 没有获得礼品盒，因为这样会导致队伍 0 或 1 获得两个礼品盒，这是严格禁止的。

$\begin{array}{lllllll} \blue 1 & \blue 1 & \blue 2 & \blue 0 & 1 & 0 \end{array}$

$\begin{array}{lllllll} 1 & \red 1 & \red 2 & \red 0 & \red 1 & 0 \end{array}$

第五个样例满足测试组 3、5 和 6 的约束。唯一可行答案是 $2\ 3$，如图所示。所有四支队伍都能收到礼品盒。

$\begin{array}{lllllll} 0 & 1 & \blue 2 & \blue 0 & 3 & 2 \end{array}$

第六个样例满足测试组 3、5 和 6 的约束。最多有五支队伍中的四支能收到礼品盒，如下所示。下标为 0、10、11 和 12 的选手（分别属于队伍 3、4、1、0）收到礼品盒。这是唯一的可行解。

$\begin{array}{lllllll} 3 & \blue 3 & \blue 3 & \blue 1 & \blue 2 & \blue 0 & \blue 3 & \blue 3 & \blue 2 & \blue 1 & 4 & 1 & 0 \end{array}$

约束与评分

• $1 \leq T < N \leq 500\,000$
• $0 \leq a_i \leq T-1$

你的解答将在一组测试组上进行评测，每组有若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。

翻译由 ChatGPT-4.1 完成。