#include<bits/stdc++.h> using namespace std; const int N=100100; int idx=0; struct node{ int z,c; }a[N]; struct kk{ int z,h; }; int d[N]; int n,Q; bool b[N]; int main() { //freopen("div.in","r",stdin); //freopen("div.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>Q; int w; for(int i=1;i<=n;i++){ cin>>w; while(idx&&a[idx].z>=w) idx--; a[++idx].z=w; a[idx].c=i; //cout<<idx<<" "<<a[idx].c<<" "; } while(Q--){ int x,y; cin>>x>>y; queue<int> q; q.push(x); memset(d,0x3f,sizeof d); memset(b,0,sizeof b); d[x]=0; b[x]=1; int ans=0x3f3f3f; while(!q.empty()){ int now=q.front(); q.pop(); b[now]=0; for(int i=1;i<=idx;i++){ int nv=now/a[i].c; if(d[nv]>=d[now]+a[i].z){ d[nv]=d[now]+a[i].z; //cout<<d[z/a[i].c]<<" "; if(!b[nv]){ q.push(nv); b[nv]=1; } } } if(now<=y) ans=min(ans,d[now]); } cout<<ans<<"\n"; } //system("grep VmPeak/proc/$PPID/status"); return 0; }