// yukicoder: No.404 部分門松列 // 2019.8.23 bal4u #include #include typedef long long ll; #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 整数の入力(負数対応) int n = 0, c = gc(); do n = 10*n + (c & 0xf), c = gc(); while (c >= '0'); return n; } void out(ll n) { // 非負整数の表示(出力) int i; char b[30]; if (!n) pc('0'); else { i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } } #define MAX 200005 //// bit木 1-indexedに注意 int bitf[MAX], bits[MAX], bitn; void add(int *bit, int i) { while (i <= bitn) bit[i]++, i += i & -i; } void sub(int *bit, int i) { while (i <= bitn) bit[i]--, i += i & -i; } int sum(int *bit, int i) { int s = 0; while (i > 0) s += bit[i], i -= i & -i; return s; } //// 本問題関連 #define MAX 200005 typedef struct { int a, id; } T; T t[MAX]; int N; int A[MAX]; int vf[MAX], vs[MAX]; ll cnt[MAX], cum[MAX]; // a[i]>=key という条件を満たす最小のi int lower_bound(int x) { int m, l = 1, r = N+1; while (l+1 < r) { m = (l+r) >> 1; if (t[m].a < x) l = m; else r = m; } return t[l].a < x? r: l; } // a[i]>key という条件を満たす最小のi int upper_bound(int x) { int m, l = 1, r = N+1; while (l+1 < r) { m = (l+r) >> 1; if (t[m].a <= x) l = m; else r = m; } return t[l].a <= x? r: l; } int cmp(const void *u, const void *v) { return ((T *)u)->a - ((T *)v)->a; } void compact(int *a, int n) { // データ圧縮。圧縮後のデータ順序は圧縮前と同様 int i, v; for (i = 1; i <= n; i++) t[i].a = a[i], t[i].id = i; qsort(t+1, n, sizeof(T), cmp); v = 1; a[t[1].id] = v; for (i = 2; i <= n; i++) { if (t[i].a != t[i-1].a) v++; a[t[i].id] = v; } } int main() { int i, x, Q; ll same; N = in(); for (i = 1; i <= N; i++) A[i] = in(); compact(A, N); // 1-indexed bitn = N+1; // bit木の初期化 // すべてのデータをとりあえずすべて後半のbit木、頻度表に登録 for (i = 1; i <= N; i++) { add(bits, A[i]); // 後半のデータをbit木に追加 vs[A[i]]++; // 後半のデータを頻度表にも追加 } same = 0; // 前後半における同じ値のデータの累積和 x = A[1], add(bitf, x), sub(bits, x); vf[x]++, vs[x]--, same += vs[x]; for (i = 2; i < N; i++) { x = A[i]; sub(bits, x), vs[x]--, same -= vf[x]; int sf = sum(bitf, x-1), ss = sum(bits, x-1); cnt[x] += (ll)sf*ss + (ll)(i-1-sf-vf[x])*(N-i-ss-vs[x]) - (same-vf[x]*vs[x]); add(bitf, x), same += vs[x], vf[x]++; } cum[0] = 0; for (i = 1; i <= N; i++) cum[i] = cum[i-1] + cnt[i]; Q = in(); while (Q--) { int L = in(), H = in(); if ((L = lower_bound(L)) > N || (H = upper_bound(H)) <= 1) pc('0'); else out(cum[A[t[H-1].id]] - cum[A[t[L].id]-1]); pc('\n'); } return 0; }