#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; 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 main() { freopen("div.in", "r", stdin); freopen("div.out", "w", stdout); 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); cout << dijkstra(x, y) << endl; } fclose(stdin); fclose(stdout); return 0; }