Problem: H: About Our Effort-About Our Effort-

problem

* I would appreciate it if you could consider this problem as an extra problem, and if possible, I would like you to enjoy the other problems first. I would like to challenge those who are willing to crush in this contest.

D Sorry for the slow query for the problem. But we weren't just neglecting. We made an effort in our own way. I have asked such a question so that you can enjoy the scale of that effort.

Problem: D Write a program that handles the server side of the problem.

Since the goal of this problem is to create a program that really meets the requirements of the D problem, we do not consider the orientation / unsuitability of each language. Those who have achieved the fastest execution speed may be adopted as a judge program when it is recorded in AOJ, so please try it.

Input format

The input is given in the following format.


N
p_1 ... p_N
Q
l_1 r_1
...
l_Q r_Q


The first row gives the length N of the permutation p. In the second line, N integers representing the permutation p are given, separated by blanks. The third line gives an integer Q that represents the number of queries. The i-th line of the following Q line consists of two integers l_i and r_i separated by blanks, indicating that the query asks for the degree of complexity of the interval [l_i, r_i].

The input satisfies the following constraints.

* 1 \ ≤ N \ ≤ 100,000
* 1 \ ≤ p_i \ ≤ N, p_i \ neq p_j (i \ neq j)
* 1 \ ≤ Q \ ≤ 200,000
* 1 \ ≤ l_i \ ≤ r_i \ ≤ N



Output format

For each Q query i, output the degree of complexity of the interval [l_i, r_i] of p to the i-line. However, the complex degree of the interval [l_i, r_i] of p is (the number of elements of \\ {(i, j) | p_i> p_j {\ rm for} l \ ≤ i <j \ ≤ r \\}). Is defined as.

Input example 1


Four
4 1 3 2
2
13
twenty four


Output example 1


2
1


Input example 2


1
1
1
1 1


Output example 2


0





Example

Input

4
4 1 3 2
2
1 3
2 4


Output

2
1

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long Int;

const int MAX_N = 100000;
const int SQRT_N = 400;

int N;
int A[MAX_N];
int P[MAX_N+1];
int E[MAX_N+1][SQRT_N+1], F[SQRT_N+1][MAX_N+1];
int G[MAX_N+1], H[MAX_N+1];
Int X[SQRT_N+1][SQRT_N+1];
int pre[SQRT_N], suf[SQRT_N];
int B_size, B_num;

//Fenwick Tree
int bit_size;
int bit[MAX_N+1];

//note that we maintain bit[1..n]
inline void init(int n){
  bit_size = n;
  memset(bit,0,sizeof(bit));
}

//add x to the i-th element
inline void inc(int i){
  while(i <= bit_size){
    bit[i]++;
    i += i & -i;
  }
}

//sum of [1..i]
inline int sum(int i){
  int res = 0;
  while(i > 0){
    res += bit[i];
    i -= i & -i;
  }
  return res;
}

//sum of [l..r]
inline int partial_sum(int l, int r){ return sum(r) - sum(l-1); }

inline void preprocess(void) {
  //Set B_size and B_num
  B_size = sqrt(N);
  //B_size = 400;
  B_num = (N + B_size-1) / B_size;

  //Step 1: make E and F
  for(int k=0;k<B_num;k++) {
    int l = k*B_size, r = min( (k+1)*B_size, N);

    memset(P,0,sizeof(P));
    for(int i=l;i<r;i++) {
      P[A[i]]++;
    }

    for(int i=0;i<N-1;i++) {
      P[i+1] += P[i];
    }

    //fill E
    int backward = 0;
    for(int i=l-1;i>=0;i--){
      backward += P[A[i]];
      E[i][k] = backward;
    }

    memset(P,0,sizeof(P));
    for(int i=l;i<r;i++) {
      P[A[i]]++;
    }

    for(int i=0;i<N-1;i++) {
      P[N-i-2] += P[N-i-1];
    }

    //fill F
    int forward = 0;
    for(int i=r;i<N;i++){
      forward += P[A[i]];
      F[k][i] = forward;
    }
  }

  //Step2-1: make G
  init(N);
  int suf_inv = 0;
  for(int i=N-1;i>=0;i--){
    suf_inv += partial_sum(1,A[i]+1);
    inc(A[i]+1);
    G[i] = suf_inv;

    if(i%B_size == 0){
      init(N);
      suf_inv = 0;
    }
  }

  //Step2-2: make H
  int pre_inv = 0;
  for(int i=0;i<N;i++){
    if(i%B_size == 0){
      init(N);
      pre_inv = 0;
    }
    pre_inv += partial_sum(A[i]+1, N);
    inc(A[i]+1);
    H[i] = pre_inv;
  }

  //Step3: make X
  for(int L=0;L<B_num;L++){
    Int inv = 0;
    for(int R=L;R<B_num;R++){
      inv += G[R*B_size];
      inv += E[L*B_size][R];
      X[L][R+1] = inv;
    }
  }

  //Step4: update E and F
  for(int k=0;k<B_num;k++){
    for(int i=0;i<k*B_size;i++){
      E[i][k] -= E[(i+B_size-1)/B_size*B_size][k];
    }
    for(int i=N-1;i>=k*B_size;i--){
      F[k][i] -= F[k][(i+1)/B_size*B_size-1];
    }
  }

  for(int i=0;i<N;i++){
    for(int k=0;k<B_num-1;k++){
      E[i][k+1] += E[i][k];
      F[k+1][i] += F[k][i];
    }
  }
}

inline void answer_query(int l, int r){
  l--;
  int L = (l+B_size-1)/B_size, R = r/B_size;
  int Ll = l, Lr = L*B_size, Rl = R*B_size, Rr = r;

  //l and r are in the same block
  if(L>=R){
    Int inv = 0;

    init(N);
    for(int i=l;i<r;i++){
      inv += partial_sum(A[i]+1, N);
      inc(A[i]+1);
    }

    printf("%lld\n", inv);
    return;
  }

  //l and r are in different blocks
  Int inv = 0;

  //inversion in consecutive blcoks
  inv += X[L][R];

  //inversion between prefix/suffix and consecutive blocks
  inv += E[l][R-1] - (L==0?0:E[l][L-1]);
  inv += F[R-1][r-1] - (L==0?0:F[L-1][r-1]);

  //inversion in prefix/suffix
  if(Ll<Lr) inv += G[l];
  if(Rl<Rr) inv += H[r-1];

  //inversion between prefix and suffix (using radix sort)

  int pn = Lr-Ll;
  for(int i=Ll;i<Lr;i++) {
    pre[i-Ll] = A[i];
  }
  sort(pre,pre+pn);
  
  int sn = Rr-Rl;
  for(int i=Rl;i<Rr;i++) {
    suf[i-Rl] = A[i];
  }
  sort(suf,suf+sn);
  
  int id_p = 0, id_s = 0;
  while(id_p<pn) {
    if(id_s == sn) {
      id_p++;
      inv += id_s;
    } else {
      if(pre[id_p] < suf[id_s]) {
	id_p++;
	inv += id_s;
      } else {
	id_s++;
      }
    }
  }

  printf("%lld\n", inv);
}

int main(){
  scanf("%d",&N);

  for(int i=0;i<N;i++) {
    scanf("%d", A+i); A[i]--;
  }

  preprocess();

  int Q;
  scanf("%d",&Q);

  while(Q--){
    int l,r;
    scanf("%d%d",&l,&r);

    answer_query(l,r);
  }
}