#include<bits/stdc++.h> using namespace std; int Q,n; const int N=5000100; int a[N]; int d[N]; bool b[N]; int top; struct node{ int m,w; }c[N]; int main(){ cin>>n>>Q; for(int i=1;i<=n;i++){ cin>>a[i]; while(top&&c[top].w>=a[i]) top--; c[++top].m=i; c[top].w=a[i]; } while(Q--){ int x,y; cin>>x>>y; memset(d,0x3f,sizeof d); memset(b,0,sizeof b); b[x]=1;d[x]=0; queue<int> q; q.push(x); int ans=0x3f3f3f; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=1;i<=top;i++){ int z=u/c[i].m; if(d[z]>d[u]+c[i].w){ d[z]=d[u]+c[i].w; if(!b[z]){ b[z]=1; q.push(z); } } } if(u<=y) ans=min(d[u],ans); } cout<<ans<<endl; } }