#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() { 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 z=q.front(); q.pop(); b[z]=0; for(int i=1;i<=idx;i++){ if(d[z/a[i].c]>d[z]+a[i].z){ d[z/a[i].c]=d[z]+a[i].z; if(!b[z/a[i].c]){ q.push(z/a[i].c); b[z/a[i].c]=1; } } } if(z<=y) ans=min(ans,d[z]); } cout<<ans<<"\n"; } }