#include<bits/stdc++.h> using namespace std; long long n,T,x,y; long long dis[100005],vis[100005],nmin,top; struct ss{ long long id,v; }b[100005]; struct sss{ long long v,w; }; queue<long long>q; inline void spfa(){ dis[x]=0,vis[x]=1,q.push(x); while(!q.empty()){ long long now=q.front(); q.pop(),vis[now]=0; if(now<=y)nmin=min(nmin,dis[now]); for(int i=1;i<=top;i++){ long long nv=now/b[i].id; if(dis[nv]>dis[now]+b[i].v){ dis[nv]=dis[now]+b[i].v; if(nv<=y)nmin=min(nmin,dis[nv]); if(vis[nv]==0){ vis[nv]=1; q.push(nv); } } } if(now<=y)nmin=min(nmin,dis[now]); } } int main(){ scanf("%lld%lld",&n,&T); for(int i=1;i<=n;i++){ long long w; scanf("%lld",&w); while(top>0 && b[top].v>=w)top--; b[++top].id=i; b[top].v=w; } while(T--){ nmin=0x3f3f3f3f3f3f3f3f; scanf("%lld%lld",&x,&y); for(int i=0;i<=x;i++){ dis[i]=0x3f3f3f3f3f3f3f3f; } if(x<=y){ printf("0\n"); continue; } spfa(); printf("%lld\n",nmin); } }