당신은 $n$개의 보석이 일렬로 나열된 퍼즐 게임을 하고 있습니다. 보석은 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호가 매겨져 있으며, $i$번째 보석의 색깔은 $c[i]$입니다.
어느 때든, 색깔이 같은 인접한 두 보석을 선택하여 제거할 수 있습니다. 보석을 제거하면 양옆의 보석들이 서로 붙어 빈 공간을 메우게 되며, 이 과정에서 새로운 인접한 쌍이 만들어질 수 있습니다.
$q$개의 독립적인 시나리오가 주어집니다. $j$번째 시나리오에서는 $l[j]$번째 보석부터 $r[j]$번째 보석까지만 고려합니다. 최적의 제거 순서를 수행한다고 가정할 때, 남길 수 있는 보석의 최소 개수는 몇 개입니까?
입력
프로그램은 표준 입력에서 읽어야 합니다. 첫 번째 줄에는 두 개의 정수 $n$과 $q$가 공백으로 구분되어 주어집니다. 두 번째 줄에는 $n$개의 정수 $c[1], c[2], \dots, c[n]$이 공백으로 구분되어 주어집니다. 다음 $q$개의 줄에는 각각 두 개의 정수가 공백으로 구분되어 주어집니다. 이 중 $i$번째 줄에는 $l[i]$와 $r[i]$가 주어집니다.
출력
프로그램은 표준 출력으로 출력해야 합니다. 출력은 $q$개의 줄로 구성되어야 합니다. $i$번째 줄에는 $i$번째 시나리오에 대한 정답인 정수 하나를 출력해야 합니다.
제한
모든 테스트 케이스에 대해 입력은 다음 범위를 만족합니다:
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ (모든 $1 \le i \le n$에 대하여)
- $1 \le l[j] \le r[j] \le n$ (모든 $1 \le j \le q$에 대하여)
프로그램은 다음 제한을 만족하는 입력 인스턴스에서 테스트됩니다:
| 서브태스크 | 점수 | 추가 제한 |
|---|---|---|
| 0 | 0 | 예제 테스트 케이스 |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | 같은 색깔의 보석들은 연속된 부분 배열을 이룸 (만약 $c[i] = c[j]$이고 $i < j$이면, $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | 모든 $1 \le j \le q$에 대하여 $l[j] = 1$ |
| 5 | 8 | 각 색깔의 보석이 정확히 두 개씩 존재함 |
| 6 | 16 | 모든 $1 \le i \le n$에 대하여 $c[i] \le 2$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | 추가 제한 없음 |
예제
입력 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
출력 1
1 0 1 4
참고
이 테스트 케이스는 서브태스크 3, 7, 8, 9에 유효합니다.
입력 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
출력 2
2 0 0
참고
이 테스트 케이스는 서브태스크 3, 6, 7, 8, 9에 유효합니다.