#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll MOD = 998244353;
const double PI = 3.141592653589793238;
int main() {
  ll N;
  cin >> N;
  vector<ll> A(N), sum(N, 0), sumsum(N, 0), maxi(N, 0);
  for (ll i = 0; i < N; ++i) {
    cin >> A[i];
    sum[i] = A[i];
    if (i != 0) sum[i] += sum[i - 1];
    sumsum[i] = sum[i];
    if (i != 0) sumsum[i] += sumsum[i - 1];
    if (i != 0) maxi[i] = maxi[i - 1];
    maxi[i] = max(maxi[i], A[i]);
  }
  for (ll k = 0; k < N; ++k) {
    cout << (k + 1) * maxi[k] + sumsum[k] << "\n";
  }
}
#include <iostream>

long sum(const long &a, const long &b) { 
	return (a + b) * (b - a + 1) / 2;
}

int main() {
	int t;
	std::cin >> t;
	while(t--) {
		long l, r;
		std::cin >> l >> r;
		long minc = l, maxc = r - l;
		if (minc > maxc) std::cout << 0 << '\n'; //if minimum of c > r - l, there is no such pair
		else std::cout << sum(r - l + 1 - maxc, r -	l + 1 - minc) << '\n';
	}
}
