# include using namespace std; typedef long long ll; const int N = 200010; ll n, cnt, godamn, q; ll a[N], b[N]; ll lt[N], rt[N]; ll c[N]; vector G[N]; vector sum(N), ans(N); map id; ll lowbit(ll x) {return x & (-x);} void add(ll x, ll ADD) { for (int i = x; i <= n; i += lowbit(i)) c[i] += ADD; } ll ask(ll x) { ll res; res = 0; for (int i = x; i; i -= lowbit(i)) res += c[i]; return res; } ll find(ll x, ll y) {return lower_bound(b, b + y, x) - b;} int main() { scanf("%lld", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]), b[i] = a[i]; sort(b, b + n); cnt = unique(b, b + n) - b; for (int i = 0; i < n; i++) a[i] = find(a[i], n); for (int i = 0; i < n; i++) G[a[i]].push_back(i); // cout << cnt << endl; // cout<<"?1\n"; for (int i = 0; i < cnt; i++) { for (int j = 0; j < G[i].size(); j++) { lt[G[i][j]] = j; rt[G[i][j]] = G[i].size() - 1 - j; // cout << lt[G[i][j]] << " " << rt[G[i][j]] << endl; } } // cout<<"?2\n"; for (int i = 0, ed; i < cnt; i++) { ed = G[i].size() - 1; for (ll j = 0; j <= ed; j++) { sum[G[i][j] + 1] += ((j + 1) * (ed - j) - j * (ed - j + 1)); // cout << G[i][j] + 1 << " " << sum[G[i][j] + 1] << endl; } } // cout<<"?3\n"; for (int i = 0; i < n; i++) { sum[i + 1] += sum[i]; ans[a[i] + 1] -= sum[i]; // cout << sum[i + 1] << " " << ans[a[i] + 1] << endl; } // cout<<"?4\n"; godamn = 0; for (int i = 0; i < cnt; i++) { for (auto x : G[i]) { ll num, num2, sum, sum2; num = ask(x); num2 = x - num - lt[x]; sum = godamn - num; sum2 = (n - 1 - x) - sum - rt[x]; ans[i + 1] += num * sum + num2 * sum2; // cout << num << " " << num2 << " " << sum << " " << sum2 << " " << ans[i + 1] << endl; } for (int j = 0; j < G[i].size(); j++) ans[i + 1] += (G[i].size() - j) * j; godamn += G[i].size(); for (auto x : G[i]) add(x + 1, 1); } // cout<<"?5\n"; for (int i = 0; i < cnt; i++) ans[i + 1] += ans[i]; scanf("%lld", &q); while (q--) { ll l, h; scanf("%lld%lld", &l, &h); printf("%lld\n", ans[find(h + 1, cnt)] - ans[find(l, cnt)]); } return 0; }