#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 z=q.front(); //cout<<z<<" "; q.pop(); b[z]=0; for(int i=1;i<=idx;i++){ //cout<<i<<" "; //cout<<a[i].c<<endl; //cout<<z/a[i].c<<" "<<d[z/a[i].c]<<" "<<d[z]<<" "<<a[i].z<<endl; if(d[z/a[i].c]>d[z]+a[i].z){ d[z/a[i].c]=d[z]+a[i].z; //cout<<d[z/a[i].c]<<" "; 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"; } return 0; }