(invert.*)

Cho dãy số nguyên \(A\) gồm \(N\) số nguyên \(A_{1},A_{2}\ldots,A_{N}\). Ta gọi cặp chỉ số (\(i,\ j\)) là một cặp nghịch thế trên dãy \(A\) nếu thỏa mãn 1 \(\leq i < j \leq N\) và \(A_{i} > A_{j}\).

Có \(Q\) yêu cầu, mỗi yêu cầu cho hai số nguyên \(L,\ R\) với 1 \(\leq L < R \leq N\), xét dãy gồm các số hạng \(A_{L},A_{L + 1},\ldots,A_{R}\). Hãy tính số cặp nghịch thế của dãy số này, tức là tính số cặp chỉ số \((i,\ j)\) thỏa mãn: \(L \leq i < j \leq R\) và \(A_{i} > A_{j}\).

Dữ liệu vào:

• Dòng thứ nhất ghi hai số nguyên dương \(N\) và \(Q\).

• Dòng thứ hai ghi \(N\) số nguyên \(A_{1},A_{2},\ldots,A_{N}\).

• \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(L\) và \(R\) (1 \(\leq L < R \leq N\)) ứng với một yêu cầu.

Kết quả: gồm \(Q\) dòng, mỗi dòng là số cặp nghịch thế ứng với mỗi yêu cầu.

Ví dụ:

Giới hạn:

• 2 \(\leq\) \(N\) \(\leq\) 1000;

• 0 \(\leq\) \(A_{i} \leq 10^{6}\) với \(i\ = \ 1,\ 2,\ 3,\ ...,\ N\);

• Có 50% số test ứng với Q = 1; L = 1, R = N;

• Có 50% số test ứng với 2 \(\leq\) Q \(\leq 10\); 1 \(\leq L < R \leq N\).