#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=1e6+5;
int a[N],cnt[N],pos[N],cnt23[N],cnt42[N],ans[N];
struct ask{
    int l,r,id;
    bool operator <(const ask &x)const{
        if(pos[l]!=pos[x.l])return pos[l]<pos[x.l];
        if(pos[l]&1)return r<x.r;return r>x.r;
    }
}q[N];
struct sqrt{
    int ans=0;
    void l_del(int x){
        cnt[a[x]]--;ans-=cnt23[a[x]/2];
        if(a[x]%4==0)cnt42[a[x]/4*3]-=cnt[a[x]/2];
        if(a[x]%2==0)cnt23[a[x]*2]-=cnt[a[x]/2*3];
    }
    void l_add(int x){
        cnt[a[x]]++;ans+=cnt23[a[x]/2];
        if(a[x]%4==0)cnt42[a[x]/4*3]+=cnt[a[x]/2];
        if(a[x]%2==0)cnt23[a[x]*2]+=cnt[a[x]/2*3];
    }
    void r_del(int x){
        cnt[a[x]]--;ans-=cnt42[a[x]];
        if(a[x]%2==0)cnt42[a[x]/2*3]-=cnt[a[x]*2];
        if(a[x]%3==0)cnt23[a[x]/3*4]-=cnt[a[x]/3*2];
    }  
    void r_add(int x){
        cnt[a[x]]++;ans+=cnt42[a[x]];
        if(a[x]%2==0)cnt42[a[x]/2*3]+=cnt[a[x]*2];
        if(a[x]%3==0)cnt23[a[x]/3*4]+=cnt[a[x]/3*2];
    }
}ds;
signed main(){
    int n=read(),m=read(),b=sqrt(n),l=1,r=0;
    for(int i=1;i<=n;i++)a[i]=read(),pos[i]=(i-1)/b+1;
    for(int i=1;i<=m;i++)q[i]={read(),read(),i};sort(q+1,q+m+1);
    for(int i=1;i<=m;i++){
        while(l<q[i].l)ds.l_del(l++);
        while(l>q[i].l)ds.l_add(--l);
        while(r>q[i].r)ds.r_del(r--);
        while(r<q[i].r)ds.r_add(++r);
        ans[q[i].id]=ds.ans;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
    return 0;
}

无法啊通过样例但是瞪了一年感觉没问题。