첫 번째 줄에 정수 N과 Q가 주어진다. (1 ≤ N ≤ 100\ 000, 1 ≤ Q ≤ 10\ 0000)

다음 N개의 줄에는 각각 한 마리의 소에 대한 품종 ID가 주어진다. 각 줄에는 1, 2, 3 중 하나의 정수가 주어지며, 줄의 i번째 값은 번호가 i인 소의 품종 ID를 의미한다.

그 다음 Q개의 줄에는 쿼리가 주어진다. 각 쿼리는 두 정수 a, b로 이루어져 있으며, a ≤ b를 만족한다. 이는 번호가 a번부터 b번까지인 소들로 이루어진 구간을 의미한다.

종류 개수 timer 2s memory 512MB

종류 개수 2s 512MB