#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define RANGE (r-l+1)
vector<int> solve(int n, vector<int>& v, int q, vector<pair<int,int>>& queries){
vector<int> ans;
ll x1[n]={}, x2[n]={}, s[n]={};
for(ll i=0; i<n; i++){
if(i>0){
x1[i]=x1[i-1];
x2[i]=x2[i-1];
s[i]=s[i-1];
}
s[i]+=v[i];
if(v[i]==1 && ((i>0 && v[i-1]==2) || (i<n-1 && v[i+1]==2))) x1[i]++;
if(v[i]==2 && ((i>0 && v[i-1]==1) || (i<n-1 && v[i+1]==1))) x2[i]++;
}
for(auto query:queries){
ll l, r;
tie(l,r)=query;
if(s[r]-((l==0)?0:s[l-1])==RANGE || s[r]-((l==0)?0:s[l-1])==2*RANGE){
ans.push_back(RANGE);
}
else{
ll c1=x1[r-1]-x1[l], c2=x2[r-1]-x2[l];
if(v[l]!=v[l+1]){
if(v[l]==1) c1++;
else c2++;
}
if(v[r]!=v[r-1]){
if(v[l]==1) c1++;
else c2++;
}
ans.push_back(min(c1,c2));
}
}
return ans;
}
