선물 상자

올해의 EGOI는 Bonn에서 개최된다. 주최 측은 대회에 참가한 각 팀에 선물 상자를 최대 하나씩 나누어 주려고 하며, 각 팀은 $0$부터 $T-1$까지의 번호로 표시된다. 참가자들은 한 줄로 서 있다. 하지만 서로 뒤섞여 있어서 같은 팀의 사람들이 서로 나란히 서 있지 않을 수도 있다. 줄에는 사람이 두 명 이상인 팀이 적어도 하나 존재한다는 점에 유의한다. 줄에는 $N$명의 사람이 있다. 사람 $i$는 팀 $a_i$에 속한다. 문제는 각 팀이 선물 상자를 최대 하나만 받아야 한다는 것이다. 절차가 원활하게 진행되도록 하기 위해, 그리고 그 결과 일부 팀이 선물을 받지 못해도 괜찮다고 생각하기 때문에, 주최 측은 선물 증정 절차를 정확히 한 번 중단하고 몇 명의 참가자를 건너뛴 뒤 선물 상자 배부를 재개하려고 한다. 즉, 참가자들의 연속한 구간 $[\ell, r]$ 하나를 건너뛴다.

모든 팀이 선물을 받을 필요는 없다. 그럼에도 주최 측은 어떤 팀도 선물을 두 개 이상 받지 않도록 하면서 선물을 받는 팀의 수를 최대화하려고 하며, 이는 이 조건에서 건너뛰는 참가자의 수를 최소화하는 것과 같다. 가능한 한 적은 수의 참가자를 건너뛰도록 선물 배부를 언제 중단하고 언제 재개하는 것이 가장 좋은지 주최 측이 결정할 수 있도록 도와달라.

제약 조건 및 채점

• $1 \leq T < N \leq 500\,000$.

• $0 \leq a_i \leq T-1$.

제출한 풀이는 각각 일정한 점수가 배정된 테스트 그룹들로 평가된다. 각 테스트 그룹은 여러 테스트 케이스로 구성된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

1 | 8 | $N = T + 1$, 즉 단 하나의 팀만 두 번 등장한다

2 | 11 | $N = 2 \cdot T$이고 모든 팀이 줄의 전반부에 정확히 한 번, 후반부에 정확히 한 번 등장한다

3 | 14 | $1 \leq T < N \leq 500$

4 | 21 | $N = 2 \cdot T$이고 모든 팀이 두 번 등장한다

5 | 22 | $1 \leq T < N \leq 5\,000$

6 | 24 | 추가 제약 조건 없음

예제

첫 번째 예제는 테스트 그룹 1, 3, 5, 6의 제약 조건을 만족한다. 아래 그림에 설명된 것처럼, 파란색 실선에 해당하는 1 1'과 빨간색 점선에 해당하는 4 4'이라는 서로 다른 두 출력이 가능하다. 어느 쪽이든 네 팀 모두 선물을 받고, 어느 팀도 선물을 하나보다 많이 받지 않는다.

두 번째 예제는 테스트 그룹 2, 3, 4, 5, 6의 제약 조건을 만족한다. 마찬가지로 아래 그림에 설명된 것처럼, 0 2'과 3 5'이라는 서로 다른 두 출력이 가능하다. 두 경우 모두 세 팀 전부가 선물을 받는다.

세 번째 예제는 테스트 그룹 3, 4, 5, 6의 제약 조건을 만족한다. 아래와 같이 세 팀이 선물을 받는 것이 최적해이다. 인덱스가 각각 $0$, $1$, $7$이고 각각 팀 $0$, $2$, $3$에 속하는 참가자들이 선물을 받는다. 이것이 유일하게 가능한 해이다.

네 번째 예제는 테스트 그룹 3, 5, 6의 제약 조건을 만족한다. 마찬가지로 아래 그림에 설명된 것처럼, 0 3'과 1 4'이라는 서로 다른 두 출력이 가능하다. 두 경우 모두 정확히 두 팀(팀 $0$와 팀 $1$)이 선물을 받는다. 팀 $2$에 선물을 주려면 팀 $0$ 또는 $1$에 선물을 두 개 주어야 하는데, 이는 엄격히 금지되므로 해당 팀은 선물을 받지 않는다.

다섯 번째 예제는 테스트 그룹 3, 5, 6의 제약 조건을 만족한다. 아래 그림에 설명된 것처럼, 가능한 답은 `2 3'뿐이다. 네 팀 모두 선물을 받는다.

여섯 번째 예제는 테스트 그룹 3, 5, 6의 제약 조건을 만족한다. 아래와 같이 다섯 팀 중 최대 네 팀이 선물을 받을 수 있다. 인덱스가 각각 $0$, $10$, $11$, $12$이고 각각 팀 $3$, $4$, $1$, $0$에 속하는 참가자들이 선물을 받는다. 이것이 유일하게 가능한 해이다.

입력의 첫 번째 줄에는 두 정수 $T$와 $N$가 주어지며, 각각 팀의 수와 줄에 있는 참가자의 수를 나타낸다.

두 번째 줄에는 $N$개의 정수 $a_i$가 주어지며, $i$번째 정수는 줄의 위치 $i$에 있는 사람이 어느 팀에 속하는지를 나타낸다. $0$부터 $T-1$까지의 모든 정수가 적어도 한 번 등장함이 보장된다.

두 정수 $\ell$와 $r$를 출력한다. 여기서 $\ell$은 처음으로 건너뛰는 사람의 인덱스이고, $r$는 마지막으로 건너뛰는 사람의 인덱스이다. $\ell$과 $r$에는 $0$부터 $N-1$까지의 인덱스가 사용된다는 점에 유의한다. 해가 둘 이상이면 그중 아무거나 하나를 출력한다.