#include #include #include #include #include using namespace std; struct BIT{ vector bit;int64_t size; BIT(int64_t n){ size=n;bit=vector(n+1); } //a[i]=x void add(int64_t i,int64_t x){ i+=1; while(i<=size)bit[i]+=x,i+=i&-i; } int64_t get(int64_t i) { return sum(i + 1) - sum(i); } //a[k] (k0)s+=bit[i],i-=i&-i; return s; } }; int N; vector a; vector ca; map compress_table; map answer_count; // aの値を圧縮するテーブルを作成する void init_compress_table() { ca = a; sort(ca.begin(), ca.end()); ca.erase(unique(ca.begin(), ca.end()), ca.end()); for(int i = 0; i < ca.size(); i++) { compress_table[ca[i]] = i; } } // aの値を圧縮する int compress(int64_t b) { assert(compress_table.count(b)); return compress_table[b]; } int main() { cin >> N; a.resize(N); for(auto &num: a) cin >> num; init_compress_table(); BIT left(N + 1), right(N + 1); for(int i = 0; i < N; i++) { right.add(compress(a[i]), 1); } long same = 0; for(int i = 0; i < N; i++) { same -= left.get(compress(a[i])) * right.get(compress(a[i])); right.add(compress(a[i]), -1); same += left.get(compress(a[i])) * right.get(compress(a[i])); // 小さいもの int64_t l_sum = left.sum(compress(a[i])); int64_t r_sum = right.sum(compress(a[i])); answer_count[a[i]] += l_sum * r_sum; // 大きいもの l_sum = left.sum(N + 1) - left.sum(compress(a[i]) + 1); r_sum = right.sum(N + 1) - right.sum(compress(a[i]) + 1); answer_count[a[i]] += l_sum * r_sum; // 同じもの(後で引く) l_sum = left.get(compress(a[i])); r_sum = right.get(compress(a[i])); answer_count[a[i]] += l_sum * r_sum; // 左右が同じものを引く answer_count[a[i]] -= same; same -= left.get(compress(a[i])) * right.get(compress(a[i])); left.add(compress(a[i]), 1); same += left.get(compress(a[i])) * right.get(compress(a[i])); } BIT answer(N + 1); for(auto t: answer_count) { answer.add(compress(t.first), t.second); } int Q; cin >> Q; for(int i = 0; i < Q; i++) { int L, H; cin >> L >> H; H ++; int64_t a = -answer.sum(lower_bound(ca.begin(), ca.end(), L) - ca.begin()); a += answer.sum(lower_bound(ca.begin(), ca.end(), H) - ca.begin()); cout << a << endl; } }