#include <bits/stdc++.h> using namespace std; int n,q; int x,y; struct node{ int v,sum; }b[100005]; int dis[100005],mp[100005]; int minn; int top=0; void dfs(){ queue<int> q; dis[x]=0; mp[x]=1; q.push(x); while (!q.empty()){ int hd=q.front(); q.pop(); mp[hd]=0; for (int i=1;i<=top;i++){ int s=hd/b[i].v; if (dis[s]>dis[hd]+b[i].sum){ dis[s]=dis[hd]+b[i].sum; if (!mp[s]){ mp[s]=1; q.push(s); } } } if (hd<=y){ minn=min(minn,dis[hd]); } } } int main(){ cin>>n>>q; for (int i=1;i<=n;i++){ int s1; cin>>s1; while (top and b[top].sum>=s1) top--; b[++top].v=i; b[top].sum=s1; } while (q--){ cin>>x>>y; minn=0x3f3f3f3f; memset(dis,0x3f3f3f3f,sizeof(dis)); if (x<=y){ cout<<0<<endl; continue; } dfs(); cout<<minn<<endl; } return 0; }