//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1E9+7;
const int MAXN=200000;
const int inf=1e18;
#ifndef khos
#define debug(...) 42
#endif
#define debug(args...) \
{ \
cout << "[" << #args << "]: "; \
my::debug::debug_out(args); \
cout << endl; \
}
namespace my::debug {
using std::cout;
template <typename T, typename = void>
struct is_container : std::false_type {};
template <typename T>
struct is_container<T, std::void_t<decltype(std::begin(std::declval<T>()))>>
: std::true_type {};
template <typename T>
constexpr bool is_container_v = is_container<T>::value;
template <typename Test, template <typename...> class Ref>
struct is_specialization : std::false_type {};
template <template <typename...> class Ref, typename... Args>
struct is_specialization<Ref<Args...>, Ref> : std::true_type {};
template <typename Test, template <typename...> class Ref>
constexpr bool is_specialization_v = is_specialization<Test, Ref>::value;
// https://stackoverflow.com/a/47563100
template <std::size_t N>
struct num {
static const constexpr auto value = N;
};
template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>) {
(func(num<Is>{}), ...);
}
template <std::size_t N, typename F>
void for_(F func) {
for_(func, std::make_index_sequence<N>());
}
template <typename T>
constexpr auto is_coutable(int)
-> decltype(std::cout << std::declval<T>(), std::true_type{}) {
return std::true_type{};
}
template <typename T>
constexpr std::false_type is_coutable(...) {
return std::false_type{};
}
template <typename T>
constexpr bool is_coutable_v = decltype(is_coutable<T>(0))::value;
template <typename T>
void single_out(T x) {
if constexpr (std::is_same_v<T, std::string> | std::is_same_v<T, char*> ||
std::is_same_v<T, const char*>) {
cout << '"' << x << '"';
} else if constexpr (std::is_same_v<T, char>) {
cout << x;
} else if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T> ||
std::is_enum_v<T> || std::is_pointer_v<T>) {
cout << x;
} else if constexpr (is_specialization_v<T, std::pair>) {
cout << "(";
single_out(x.first);
cout << ", ";
single_out(x.second);
cout << ")";
} else if constexpr (is_specialization_v<T, std::tuple>) {
cout << "(";
std::string sep = "";
for_<std::tuple_size_v<T>>([&](auto i) {
cout << exchange(sep, ", ");
single_out(std::get<i.value>(x));
});
cout << ")";
} else if constexpr (is_specialization_v<T, std::map> ||
is_specialization_v<T, std::unordered_map>) {
cout << "{";
std::string sep = "";
for (auto [k, v] : x) {
cout << exchange(sep, ", ");
single_out(k);
cout << ": ";
single_out(v);
}
cout << "}";
} else if constexpr (is_container_v<T>) {
if constexpr (is_specialization_v<T, std::vector>) {
cout << "[";
} else cout << "{";
std::string sep = "";
for (auto i : x) {
cout << exchange(sep, ", ");
single_out(i);
}
if constexpr (is_specialization_v<T, std::vector>) {
cout << "]";
} else cout << "}";
}
// types without iterator, f*** you, c++ comittee
else if constexpr (is_specialization_v<T, std::queue>) {
cout << "{";
std::string sep = "";
while (x.size()) {
cout << exchange(sep, ", ");
single_out(x.front());
x.pop();
}
cout << "}";
} else if constexpr (is_specialization_v<T, std::stack> ||
is_specialization_v<T, std::priority_queue>) {
std::vector<
std::remove_cv_t<std::remove_reference_t<decltype(x.top())>>>
v;
while (x.size()) {
v.push_back(x.top());
x.pop();
}
if constexpr (is_specialization_v<T, std::stack>)
std::reverse(v.begin(), v.end());
cout << "{";
std::string sep = "";
for (auto i : v) {
cout << exchange(sep, ", ");
single_out(i);
}
cout << "}";
}
// lastly, if the expression (cout << x) compiles, use it
else {
static_assert(is_coutable_v<T>, "The type given to debug() is not supported.");
cout << x;
}
}
template <typename T, typename... Rest>
void debug_out(T, Rest...);
void debug_out();
template <typename T, typename... Rest>
void debug_out(T x, Rest... rest) {
// single_out<std::remove_cv_t<std::decay_t<T>>>(x);
single_out<std::remove_cv_t<T>>(x);
if (sizeof...(rest) > 0) cout << ", ";
debug_out(rest...);
}
void debug_out() {
}
}; // namespace my::debug
struct LazySegTree {
int n;
vector<long long> tree, lazy;
LazySegTree(int size) {
n = size;
tree.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
void push(int v, int l, int r) {
if (lazy[v] != 0) {
tree[v] = lazy[v] * (r - l + 1);
if (l != r) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
}
void update(int v, int l, int r, int ql, int qr, long long val) {
push(v, l, r);
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
lazy[v] += val;
push(v, l, r);
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, val);
update(2 * v + 1, m + 1, r, ql, qr, val);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
long long query(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[v];
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void update(int l, int r, long long val) {
update(1, 0, n - 1, l, r, val);
}
long long query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
void solution(){
int n,d;
cin >> n >> d;
vi<int> a(n);
for (auto &x : a) cin >> x;
vi<vi<pair<int,int>>> qry(n);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int l,r;
cin >> l >> r;
--l, --r;
qry[r].push_back({l, i});
}
vi<int> pref(n);
pref[0] = a[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + a[i];
}
// debug(pref);
LazySegTree sg(n);
stack<pair<int,int>> sk;
sk.push({0, -1});
vi<int> ans(q);
for(int i=0; i<n; i++){
while (!sk.empty() && sk.top().ff > a[i]) sk.pop();
sg.update(sk.top().ss + 1, i, a[i]);
for (auto [l, id] : qry[i]) {
ans[id] = pref[i] - (l ? pref[l - 1] : 0) - sg.query(l, i);
}
sk.push({a[i], i});
}
for (auto x : ans) cout << x << '\n';
}
int32_t main(){
clock_t tStart = clock();
#ifdef khos
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
#ifdef TESTCASES
// cin >> q;
#endif
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
