CERN

CERN은 핵물리학과 기본 입자 물리학을 연구하는 국제 기관이다. CERN의 입자 가속기 시스템은 입자를 고속으로 충돌시키는 실험에 쓰인다.

일렬로 놓인 $N$개의 입자가 있다. 각 입자에는 종류 $v_i$가 있으며, $v_i$는 $1$ 이상 $N$ 이하의 자연수이다.

$Q$번의 실험을 진행한다. $i$번째 실험에서는 $l_i$번째 입자부터 $r_i$번째 입자까지를 관찰한다($l_i < r_i$). 관찰 대상 입자 중 종류가 다른 입자 두 개를 골라 충돌시킬 수 있다. 그러면 두 입자는 모두 소멸한다. 관찰 대상에 종류가 다른 입자가 두 개 이상 남아 있는 동안 이 과정을 반복한다. 실험은 관찰 대상 입자가 모두 소멸하거나, 한 종류의 입자만 남은 상태에서 끝난다. 어떤 입자를 어떤 순서로 충돌시키느냐에 따라 마지막에 남는 입자의 종류가 달라질 수 있다.

충돌에는 비용이 크므로, 이 실험은 이론으로만 진행한다. 각 실험에 대해, 실험이 끝났을 때 그 종류의 입자가 몇 개 남은 상태로 끝날 수 있는 입자 종류의 수를 구하라.

첫째 줄에 입자의 수 $N$과 실험의 수 $Q$가 주어진다.

둘째 줄에 입자의 종류 $v_1, \dots, v_N$이 순서대로 주어진다.

이어지는 $Q$개의 줄에는 각각 $i$번째 실험에서 관찰하는 구간을 나타내는 두 자연수 $l_i$와 $r_i$가 주어진다($1 \le l_i < r_i \le N$).

$Q$번의 실험마다 실험이 끝났을 때 남을 수 있는 입자 종류의 수를 한 줄에 하나씩 출력한다.

모든 서브태스크에서 $2 \le N \le 500000$이고 $1 \le Q \le 500000$이다.

첫 번째 실험에서는 종류 3과 종류 4의 입자를 충돌시킬 수 있다. 그러면 종류 2의 입자 두 개가 남는다. 다른 종류의 입자가 남는 방법은 없다.

두 번째 실험에서는 모든 종류의 입자가 일정한 개수만큼 남도록 할 수 있다.

네 번째와 다섯 번째 실험에서는 충돌을 어떻게 선택하든 종류 4의 입자가 일정한 개수만큼 남는다.