다양성

Zoran은 자그레브 동물원의 사육사이다. 그는 방문객의 만족도와 동물을 전시하는 방식 사이의 관계를 연구하고 있다. 방문객이 동물원 전체를 걷는 경로는 $N$개의 서식지로 이루어진 수열로 볼 수 있으며, 각 서식지에는 한 종의 동물이 들어 있다. $i$번째 서식지에는 처음에 종 $a_i$의 동물이 있고, 방문객은 서식지를 순서대로 관람한다. Zoran은 동물의 배치를 바꾸기 시작했고, 방문객은 경로의 총 다양성이 작을수록 만족한다는 것을 알게 되었다.

서식지 수열의 다양성은 그 안에서 관찰되는 서로 다른 동물 종의 수이다. 수열의 총 다양성은 연속 부분 수열 각각의 다양성을 모두 더한 값이다. 예를 들어 수열 (1, 1, 2)의 다양성은 2이다. 이 수열의 연속 부분 수열 (1), (1), (2), (1, 1), (1, 2), (1, 1, 2)의 다양성은 각각 1, 1, 1, 1, 2, 2이므로, 총 다양성은 8이다.

Zoran은 서로 독립적인 $Q$개의 질의에 대한 답을 알고 싶어 한다. $i$번째 질의에서는 $l_i$번째 서식지부터 $r_i$번째 서식지까지의 연속 구간을 본다. 이 구간의 동물을 재배열했을 때 얻을 수 있는 총 다양성의 최솟값을 구해야 한다. 각 질의는 원래 배치 $a_i$를 기준으로 독립적으로 생각한다.

첫 줄에 정수 $N$과 $Q$가 주어진다. 둘째 줄에는 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 주어지며, $a_i$는 $i$번째 서식지에 있는 동물의 종이다. 이어지는 $Q$개의 줄에는 각각 질의를 나타내는 정수 $l_i$와 $r_i$($1 \le l_i \le r_i \le N$)가 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 총 다양성 최솟값을 출력한다.