//?

//? https://ac.nowcoder.com/acm/contest/20322/J

#include <algorithm>

#include <iostream>

#include <cstring>

?using namespace std;

const int N = 1E5 + 100;

int n, m, block;

int arr[N]={ 0,1, 2, 3,4, 1,2,3 };

/*? 莫隊(duì)算法 (Mo's Algorithm)

*/

int res[N];

?int cnt[N];

struct Mo {

? ? int L, r, idx, lb;??

? ? ?bool operator < (const Mo &rhs) const {

? ? ? ? if (lb == rhs.lb) {

? ? ? ? ? ? return r < rhs.r;

? ? ? ? }

? ? ? ? return lb < rhs.lb;

? ? }

};

Mo qry[N];

int Q[N][2]={

1, 3,

3, 6,

2 ,3,

2 ,4,

1 ,3,

1 ,7,

3,5

};

?int sum=0;

void Insert(int x)

{

? ? cnt[x]++;//個(gè)數(shù)記錄

? ? if(cnt[x]==1) sum++;//如果滿足條件，就更新答案

}

void Remove(int x)

{

? ? cnt[x]--;

? ? if(cnt[x]==0) sum--;

}

int main() {

? ? ? n=7;m=7;

memset(cnt,0,sizeof cnt);

? ? /*

cin >> n>> m;

? ? for (int i = 1; i <= n; i++) {

? ? ? ? cin >> arr[i];

? ? }

? ? ?

? ? for (int i = 1; i <= m; i++) {

? ? ? ? cin >> qry[i].L?>> qry[i].r;

? ? ? ? qry[i].idx?= i;

? ? }*/

block = sqrt(n); ?

cout<<block<<endl;

for (int i = 1; i <= m; i++) {

? ? ? ? ?qry[i].L =Q[i-1][0]; qry[i].r=Q[i-1][1];

? ? ? ? qry[i].idx = i;

qry[i].lb= qry[i].L/block;

}

? ?

? ?sort(qry + 1, qry + 1 + m);

for (int i = 1; i <= m; i++) cout<<qry[i].idx<<"? ?";

cout<<endl;

? ? int left=0,r=n+1;

? ? for (int i = 1; i <= m; i++) {? ? ? ??

while(left<qry[i].L) Insert(arr[++left]);

cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;? ? ? ? ?

while(left>qry[i].L) Remove(arr[left--]);

? ? ? ? ? ?cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

? ? ? ? ? ? while(r<qry[i].r) Remove(arr[r++]);

? ? ? ? ? ?cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

? ? ? ? ? ? while(r>qry[i].r) Insert(arr[--r]);

cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl<<endl;

? ? ? ? ? ? res[qry[i].idx]=sum;//記錄答案

? ? }

? ? for (int i = 1; i <= m; i++) {

? ? ? ? cout << res[i] << endl;

? ? }

? ? return 0;

}