rt，WA求调

• 如果区间最小值=区间gcd，ans=r-l+1-最小值的数量

• 用线段树维护区间最小值和她的数量，ST表维护区间gcd（指最大公约数）

• st-gcd没有挂，放板子题里测过了

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>

#define ll long long
#define db double
#define MAX 0x7fffffff
#define init inline int
#define INF 0X3fffffff
#define N 400001>>1

using namespace std;

inline long long read()
{
    ll f=1,s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*f;
}

ll n,a[100001],m,x,y;
ll f[100001][20],lg[100001];

struct node{
	ll num,min;
}s[100001];

node pushup(node l,node r){
	node t;
	t.min=min(l.min,r.min);
	t.num=(l.min==t.min?l.num:0)+(r.min==t.min?r.num:0);
	return t;
}

void build(ll k,ll l,ll r){
//	cout<<k<<" "<<l<<" "<<r<<endl;
	if(l==r) {s[k].min=a[l],s[k].num=1;return;}
	ll mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	s[k]=pushup(s[k<<1],s[k<<1|1]);
}

node query(ll k,ll l,ll r,ll x,ll y){
	if(l>y||x>r) return (node){0,0};
	if(x<=l&&r<=y) return s[k];
	ll mid=l+r>>1;
	return pushup(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
}

ll gcd(ll x,ll y){
	if(!y) return x;
	return gcd(y,x%y);
}

void ST(){
	for(int j=1;j<=lg[n]+5;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

ll sgcd(ll x,ll y){
	ll s=lg[y-x+1];
	return gcd(f[x][s],f[y-(1<<s)+1][s]);
}

int main(){
	n=read();lg[0]=-1;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
		lg[i]=lg[i>>1]+1;
	}
	ST();build(1,1,n);
	m=read();
	while(m-->0){
		x=read();y=read();
		node q=query(1,1,n,x,y);
		ll GCD=sgcd(x,y);
		cout<<y-x+1-(q.min==GCD?q.num:0)<<endl;
	}
	return 0;
}