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