代码：

#include<bits/stdc++.h>
using namespace std;
#define R register
#define ri register int
#define ll long long
#define ull unsigned long long
#define lid (id<<1)
#define rid (id<<1|1)
#define _gcd(a,b) abs(__gcd(a,b))
void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int read();
inline void write(int ans);
inline void put(int x,char c);
const int N=2e5,inf=1e9;
int n,m;
int a[N];
struct tre{
	int minx;
	int sum;
	int gcd;
	int l,r,mlr,lr;
}tree[N];
struct seg{
	int minx;
	int sum;
	int gcd;
};
void pushup(int id){
	tree[id].minx=min(tree[lid].minx,tree[rid].minx);
	tree[id].sum=0;
	if(tree[lid].minx==tree[id].minx)tree[id].sum+=tree[lid].sum;
	if(tree[rid].minx==tree[id].minx)tree[id].sum+=tree[rid].sum;
	tree[id].gcd=_gcd(tree[lid].gcd,tree[rid].gcd);
	return ;
}
void build(int id,int l,int r){
	tree[id].l=l,tree[id].r=r;
	if(l==r){
		tree[id].gcd=tree[id].minx=a[l];
		tree[id].sum=1;
		return;
	}
	int mid=l+r>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	pushup(id);
	return;
}
seg query(int id,int l,int r){
	if(tree[id].l>r||tree[id].r<l)return (seg){inf,0,0};
	if(tree[id].l>=l&&tree[id].r<=r){
		return (seg){tree[id].minx,tree[id].sum,tree[id].gcd};
	}
	seg l1=query(lid,l,r),r1=query(rid,l,r);
	int sum=0,mx=min(l1.minx,r1.minx);
	if(l1.minx==mx)sum+=l1.sum;
	if(r1.minx==mx)sum+=r1.sum;
	return (seg){mx,sum,_gcd(l1.gcd,r1.gcd)};
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	m=read();
	build(1,1,n);
	while(m--){
		int l=read(),r=read();
		seg tmp=query(1,l,r);
		int ans=r-l+1;
		if(tmp.minx==tmp.gcd){
			ans-=tmp.sum;
		}
		printf("%d\n",ans);
	}
	return 0;
}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x % 10+'0');return;}
inline void put(int x,char c){write(x);putchar(c);return;}

似乎建树的时候T了