#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std; int n, q, cnt; int dis[100010]; int vis[100010]; struct edge { int y, w; } ; edge p[100010]; struct node { int x, d; bool operator < (const node & b) const { return d > b.d; } } ; int dijkstra(int s, int t) { priority_queue<node> q; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); q.push((node){s, 0}); dis[s] = 0; int ans = 0x3f3f3f3f; while (q.size()) { int x = q.top().x; q.pop(); if (vis[x]) continue; vis[x] = 1; if (x <= t) ans = min(ans, dis[x]); for (int i = 1; i <= cnt; i++) { if (dis[x / p[i].y] > dis[x] + p[i].w) { dis[x / p[i].y] = dis[x] + p[i].w; q.push((node){x / p[i].y, dis[x / p[i].y]}); } } } return ans; } /*int spfa(int s, int t) { queue<int> q; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); q.push(s); dis[s] = 0; vis[s] = 1; int ans = 0x3f3f3f3f; while (q.size()) { int x = q.front(); q.pop(); vis[x] = 0; for (int i = 1; i <= cnt; i++) { int y = x / p[i].y; if (dis[y] > dis[x] + p[i].w) { dis[y] = dis[x] + p[i].w; if (vis[y] == 0) { q.push(y); vis[y] = 1; } } } if (x <= t) ans = min(ans, dis[x]); } return ans; }*/ int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) { int w; scanf("%d", &w); while (cnt != 0 && p[cnt].w >= w) cnt--; p[++cnt] = (edge){i, w}; } while (q--) { int x, y; scanf("%d %d", &x, &y); printf("%d\n", spfa(x, y)); } return 0; }