Background

Problem Description

You are given a sequence $a$ of length $n$ and $m$ queries. For each query, you need to find the number of inversion pairs in a given interval.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers representing the sequence.

Then follow $m$ lines, each containing two integers representing the query interval.

Output Format

Output $m$ lines, each with one integer representing the answer to the query.

4 1
1 4 2 3
2 4

2

Hint

$1 \leq n, m \leq 10^5$, $0 \leq a_i \leq 10^9$.

We already have an algorithm faster than $n^{1.5}$.

Source
By nzhtl1477

Translated by ChatGPT 5