#include<bits/stdc++.h> using namespace std; int n,T,x,y,w; int dis[100005],nmin,top; bool vis[100005]; 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++){ 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); memset(dis,0x3f,sizeof(dis)); 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); } }