//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
#include "partition.h"
#include <vector>
vector<int> aa;
vector<int> bb;
int n;
set<int> xx;
map<int,int> yy;
vector<int> pre[100001];
void init(int nn, vector<int> aaa, vector<int> bbb) {
aa=aaa;
bb=bbb;
n=nn;
for(auto j:aa){
xx.insert(j);
}
int ind=0;
for(auto j:xx){
yy[j]=ind;
ind++;
}
for(int j=0;j<n;j++){
pre[yy[aa[j]]].pb(j);
aa[j]=yy[aa[j]];
}
}
map<pair<int,int>,int> ans2;
int count_partition(int x, int y) {
if(xx.find(x)==xx.end()){
return 1;
}
x=yy[x];
if(ans2.find({x,y})!=ans2.end()){
return ans2[{x,y}];
}
int ans=0;
int la=-1;
int la2=-1;
int co=0;
int st=1;
while(true){
int ind=lower_bound(pre[x].begin(),pre[x].end(),la2+bb[y-1])-pre[x].begin();
if(ind==pre[x].size()){
break;
}
ind=max(ind,la+y);
if(ind>=pre[x].size()){
break;
}
if(pre[x][ind]==n-1){
st=0;
}
ans++;
la2=pre[x][ind];
la=ind;
}
ans+=st;
ans2[{x,y}]=ans;
/*int co=0;
int co2=0;
int ans=0;
for(int i=0;i<n;i++){
if(aa[i]==x){
co++;
}
co2++;
if(co>=y and co2>=bb[y-1] and aa[i]==x){
ans++;
co=0;
co2=0;
}
else if(i==n-1){
ans++;
}
}*/
/*int ans=(pre[x].size()/y);
if(((int)(pre[x].size()%y))>0 or pre[x].back()!=n-1){
ans++;
}*/
/*int ans=((int)pre[x].size()+bb[y-1]-1)/bb[y-1];*/
return ans;
}
Ly8jcHJhZ21hIEdDQyBvcHRpbWl6ZSgiT2Zhc3QsdW5yb2xsLWxvb3BzIikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsbzsKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBhIGZpcnN0IAojZGVmaW5lIGIgc2Vjb25kCi8vI2RlZmluZSBlbmRsICdcbicKCiNpbmNsdWRlICJwYXJ0aXRpb24uaCIKCiNpbmNsdWRlIDx2ZWN0b3I+CnZlY3RvcjxpbnQ+IGFhOwp2ZWN0b3I8aW50PiBiYjsKaW50IG47CnNldDxpbnQ+IHh4OwptYXA8aW50LGludD4geXk7CnZlY3RvcjxpbnQ+IHByZVsxMDAwMDFdOwp2b2lkIGluaXQoaW50IG5uLCB2ZWN0b3I8aW50PiBhYWEsIHZlY3RvcjxpbnQ+IGJiYikgewoJYWE9YWFhOwoJYmI9YmJiOwoJbj1ubjsKCWZvcihhdXRvIGo6YWEpewoJCXh4Lmluc2VydChqKTsKCX0KCWludCBpbmQ9MDsKCWZvcihhdXRvIGo6eHgpewoJCXl5W2pdPWluZDsKCQlpbmQrKzsKCX0KCWZvcihpbnQgaj0wO2o8bjtqKyspewoJCXByZVt5eVthYVtqXV1dLnBiKGopOwoJCWFhW2pdPXl5W2FhW2pdXTsKCX0KCgoKCgoKfQptYXA8cGFpcjxpbnQsaW50PixpbnQ+IGFuczI7CmludCBjb3VudF9wYXJ0aXRpb24oaW50IHgsIGludCB5KSB7CglpZih4eC5maW5kKHgpPT14eC5lbmQoKSl7CgkJcmV0dXJuIDE7Cgl9Cgl4PXl5W3hdOwoJaWYoYW5zMi5maW5kKHt4LHl9KSE9YW5zMi5lbmQoKSl7CgkJcmV0dXJuIGFuczJbe3gseX1dOwoJfQoJCglpbnQgYW5zPTA7CglpbnQgbGE9LTE7CglpbnQgbGEyPS0xOwoJaW50IGNvPTA7CglpbnQgc3Q9MTsKCXdoaWxlKHRydWUpewoKCQlpbnQgaW5kPWxvd2VyX2JvdW5kKHByZVt4XS5iZWdpbigpLHByZVt4XS5lbmQoKSxsYTIrYmJbeS0xXSktcHJlW3hdLmJlZ2luKCk7CgkJaWYoaW5kPT1wcmVbeF0uc2l6ZSgpKXsKCQkJYnJlYWs7CgkJfQoJCWluZD1tYXgoaW5kLGxhK3kpOwoJCWlmKGluZD49cHJlW3hdLnNpemUoKSl7CgkJCWJyZWFrOwoJCX0KCQlpZihwcmVbeF1baW5kXT09bi0xKXsKCQkJc3Q9MDsKCQl9CgkJYW5zKys7CgkJbGEyPXByZVt4XVtpbmRdOwoJCWxhPWluZDsKCX0KCWFucys9c3Q7CglhbnMyW3t4LHl9XT1hbnM7CgkvKmludCBjbz0wOwoJaW50IGNvMj0wOwoJaW50IGFucz0wOwoJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJaWYoYWFbaV09PXgpewoJCQljbysrOwoJCX0KCQljbzIrKzsKCQlpZihjbz49eSBhbmQgY28yPj1iYlt5LTFdIGFuZCBhYVtpXT09eCl7CgkJCWFucysrOwoJCQljbz0wOwoJCQljbzI9MDsKCQl9CgkJZWxzZSBpZihpPT1uLTEpewoJCQlhbnMrKzsKCQl9Cgl9Ki8KCS8qaW50IGFucz0ocHJlW3hdLnNpemUoKS95KTsKCWlmKCgoaW50KShwcmVbeF0uc2l6ZSgpJXkpKT4wIG9yIHByZVt4XS5iYWNrKCkhPW4tMSl7CgkJYW5zKys7Cgl9Ki8KCgkvKmludCBhbnM9KChpbnQpcHJlW3hdLnNpemUoKStiYlt5LTFdLTEpL2JiW3ktMV07Ki8KCgoKCglyZXR1cm4gYW5zOwp9Cg==