#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; }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); scanf("%d%d",&n,&T); for(int i=1;i<=n;i++){ int w; scanf("%d",&w); while(top && b[top].v>=w)top--; b[++top].id=i; b[top].v=w; } while(T--){ nmin=0x3f3f3f3f; scanf("%d%d",&x,&y); for(int i=0;i<=x;i++){ dis[i]=0x3f3f3f3f; } if(x<=y){ printf("0\n"); continue; } queue<int>q; dis[x]=0,vis[x]=1,q.push(x); while(!q.empty()){ int now=q.front(); q.pop(),vis[now]=0; 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(vis[nv]==0){ vis[nv]=1; q.push(nv); } } } if(now<=y)nmin=min(nmin,dis[now]); } printf("%d\n",nmin); } }