#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int upLimit, sqN, BIT[32768] = {};
bool sortFunc(pii a, pii b) {
if (a.first / sqN == b.first / sqN) {
return a.second < b.second;
}
return a.first/sqN < b.first/sqN;
}
int query(int x) {
int sum = 0;
for (; x > 0; x -= (x&(-x))) {
sum += BIT[x];
}
return sum;
}
void update(int x, int val) {
for (; x <= upLimit; x += (x&(-x))) {
BIT[x] += val;
}
}
void print(vector<int> nums) {
for (int num: nums) {
cout<<num<<" ";
}cout<<endl;
}
void solve(vector<int> nums, vector<pii> sortedQueries) {
print(nums);
int prevL = 1, prevR = 1, curInvs = 0;
update(nums[1], 1);
for (pii q: sortedQueries) {
cout<<q.first<<" "<<q.second<<endl;
while (prevL < q.first) {
update(nums[prevL], -1);
// ct of nums which are smaller than nums[prevL]
curInvs -= (query(nums[prevL] - 1));
prevL++;
}
while (prevL > q.first) {
prevL--;
update(nums[prevL], 1);
curInvs += query(nums[prevL] - 1);
}
while (prevR > q.second) {
update(nums[prevR], -1);
curInvs -= (query(upLimit) - query(nums[prevR]));
prevR--;
}
while (prevR < q.second) {
prevR++;
update(nums[prevR], 1);
curInvs += (query(upLimit) - query(nums[prevR]));
}
cout<<curInvs<<endl;
}
}
int main() {
// your code goes here
int n, num, l, r;
cin>>n;
upLimit = n;
vector <int> nums(n+1);
vector <pii> queries, mappedNums;
for (int i = 0; i < n; i++) {
cin>>num;
mappedNums.push_back({num, i + 1});
}
sort(mappedNums.begin(), mappedNums.end());
nums[0]=0;
for (int i = 0; i < n; i++) {
nums[mappedNums[i].second] = i + 1;
}
sqN = sqrt(n);
int q;
cin >> q;
while (q--) {
cin >> l >> r;
queries.push_back({l, r});
}
sort(queries.begin(), queries.end(), sortFunc);
solve(nums, queries);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKCmludCB1cExpbWl0LCBzcU4sIEJJVFszMjc2OF0gPSB7fTsKCmJvb2wgc29ydEZ1bmMocGlpIGEsIHBpaSBiKSB7CglpZiAoYS5maXJzdCAvIHNxTiA9PSBiLmZpcnN0IC8gc3FOKSB7CgkJcmV0dXJuIGEuc2Vjb25kIDwgYi5zZWNvbmQ7Cgl9CglyZXR1cm4gYS5maXJzdC9zcU4gPCBiLmZpcnN0L3NxTjsKfQppbnQgcXVlcnkoaW50IHgpIHsKCWludCBzdW0gPSAwOwoJZm9yICg7IHggPiAwOyB4IC09ICh4JigteCkpKSB7CgkJc3VtICs9IEJJVFt4XTsKCX0KCXJldHVybiBzdW07Cn0Kdm9pZCB1cGRhdGUoaW50IHgsIGludCB2YWwpIHsKCWZvciAoOyB4IDw9IHVwTGltaXQ7IHggKz0gKHgmKC14KSkpIHsKCQlCSVRbeF0gKz0gdmFsOwoJfQp9CnZvaWQgcHJpbnQodmVjdG9yPGludD4gbnVtcykgewoJZm9yIChpbnQgbnVtOiBudW1zKSB7CgkJY291dDw8bnVtPDwiICI7Cgl9Y291dDw8ZW5kbDsKfQp2b2lkIHNvbHZlKHZlY3RvcjxpbnQ+IG51bXMsIHZlY3RvcjxwaWk+IHNvcnRlZFF1ZXJpZXMpIHsKCXByaW50KG51bXMpOwoJaW50IHByZXZMID0gMSwgcHJldlIgPSAxLCBjdXJJbnZzID0gMDsKCXVwZGF0ZShudW1zWzFdLCAxKTsKCWZvciAocGlpIHE6IHNvcnRlZFF1ZXJpZXMpIHsKCQljb3V0PDxxLmZpcnN0PDwiICI8PHEuc2Vjb25kPDxlbmRsOwoJCXdoaWxlIChwcmV2TCA8IHEuZmlyc3QpIHsKCQkJdXBkYXRlKG51bXNbcHJldkxdLCAtMSk7CgkJCS8vIGN0IG9mIG51bXMgd2hpY2ggYXJlIHNtYWxsZXIgdGhhbiBudW1zW3ByZXZMXQoJCQljdXJJbnZzIC09IChxdWVyeShudW1zW3ByZXZMXSAtIDEpKTsKCQkJcHJldkwrKzsKCQl9CgkJd2hpbGUgKHByZXZMID4gcS5maXJzdCkgewoJCQlwcmV2TC0tOwoJCQl1cGRhdGUobnVtc1twcmV2TF0sIDEpOwoJCQljdXJJbnZzICs9IHF1ZXJ5KG51bXNbcHJldkxdIC0gMSk7CgkJCQoJCX0KCQl3aGlsZSAocHJldlIgPiBxLnNlY29uZCkgewoJCQl1cGRhdGUobnVtc1twcmV2Ul0sIC0xKTsKCQkJY3VySW52cyAtPSAocXVlcnkodXBMaW1pdCkgLSBxdWVyeShudW1zW3ByZXZSXSkpOwoJCQlwcmV2Ui0tOwoJCX0KCQl3aGlsZSAocHJldlIgPCBxLnNlY29uZCkgewoJCQlwcmV2UisrOwoJCQl1cGRhdGUobnVtc1twcmV2Ul0sIDEpOwoJCQljdXJJbnZzICs9IChxdWVyeSh1cExpbWl0KSAtIHF1ZXJ5KG51bXNbcHJldlJdKSk7CgkJfQoJCWNvdXQ8PGN1ckludnM8PGVuZGw7Cgl9Cn0KCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IG4sIG51bSwgbCwgcjsKCWNpbj4+bjsKCXVwTGltaXQgPSBuOwoJdmVjdG9yIDxpbnQ+IG51bXMobisxKTsKCXZlY3RvciA8cGlpPiBxdWVyaWVzLCBtYXBwZWROdW1zOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQljaW4+Pm51bTsKCQltYXBwZWROdW1zLnB1c2hfYmFjayh7bnVtLCBpICsgMX0pOwoJfQoJc29ydChtYXBwZWROdW1zLmJlZ2luKCksIG1hcHBlZE51bXMuZW5kKCkpOwoJbnVtc1swXT0wOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQludW1zW21hcHBlZE51bXNbaV0uc2Vjb25kXSA9IGkgKyAxOwoJfQoJCglzcU4gPSBzcXJ0KG4pOwoJaW50IHE7CgljaW4gPj4gcTsKCXdoaWxlIChxLS0pIHsKCQljaW4gPj4gbCA+PiByOwoJCXF1ZXJpZXMucHVzaF9iYWNrKHtsLCByfSk7Cgl9Cglzb3J0KHF1ZXJpZXMuYmVnaW4oKSwgcXVlcmllcy5lbmQoKSwgc29ydEZ1bmMpOwoJc29sdmUobnVtcywgcXVlcmllcyk7CglyZXR1cm4gMDsKfQ==