No Time to Dry

Bessie는 최근 페인트 세트를 받았고, 목초지 한쪽 끝에 있는 긴 울타리를 칠하려고 한다. 울타리는 1미터 길이의 연속한 $N$개 구간으로 이루어져 있다 ($1\le N\le 2\cdot 10^5$). Bessie에게는 $N$가지 색이 있고, 색의 어두운 정도가 커지는 순서대로 $1$부터 $N$까지의 문자로 나타낸다 ($1$은 매우 밝은 색이고 $N$은 매우 어두운 색이다). 따라서 각 울타리 구간에 칠하고 싶은 색을 $N$개의 정수로 이루어진 배열로 표현할 수 있다.

처음에는 모든 울타리 구간이 칠해지지 않은 상태이다. Bessie는 밝은 색 위에 어두운 색만 칠할 수 있다는 조건 아래에서, 연속한 구간을 한 가지 색으로 한 번의 붓질로 칠할 수 있다.

예를 들어, 처음에 칠해지지 않은 길이 4인 구간은 다음과 같이 칠할 수 있다.

0000 -> 1110 -> 1122 -> 1332

안타깝게도 Bessie는 페인트가 마르기를 기다릴 시간이 없다. 그래서 일부 울타리 구간은 칠하지 않고 남겨 두어야 할 수도 있다고 생각한다. 현재 Bessie는 $Q$개의 후보 범위를 고려하고 있고 ($1\le Q\le 2\cdot 10^5$), 각 범위는 칠하려는 구간 $a \ldots b$의 양 끝 인덱스를 나타내는 두 정수 $(a,b)$로 주어진다 ($1 \leq a \leq b \leq N$).

각 후보 범위에 대해, 범위 밖의 모든 울타리 구간은 칠하지 않은 채로 두면서 범위 안의 모든 울타리 구간을 원하는 색으로 칠하는 데 필요한 최소 붓질 횟수는 얼마인가? Bessie는 이 과정에서 실제로 칠하지 않으므로, 각 후보 범위의 답은 서로 독립적이다.

첫 번째 줄에 $N$과 $Q$가 주어진다.

다음 줄에 각 울타리 구간에 원하는 색을 나타내는 $N$개의 정수 배열이 주어진다.

다음 $Q$개의 줄에 각각 후보 범위를 나타내는 두 정수 $a$와 $b$가 공백으로 구분되어 주어진다.

$Q$개의 후보 각각에 대해 답을 새로운 줄에 출력한다.