B. Number of Inversions
time limit per test
5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

An array of $$$n$$$ integers and $$$q$$$ queries are given. Each query consists of two integers $$$(l, r)$$$:

  1. Reverse the subarray from index $$$l$$$ to $$$r$$$.
  2. Output the number of inversions in the entire array.
  3. Restore the array to its original state (i.e., the array as it was before this query)
Note: An inversion in an array is a pair of indices $$$(i, j)$$$ such that $$$i \lt j$$$ and $$$a_i \gt a_j$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ — the size of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the initial elements of the array.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ — the interval $$$[l, r]$$$

  • $$$1 \leq n, q \leq 10^5$$$
  • $$$1 \leq a_i \leq n$$$
  • $$$1 \leq l \leq r \leq n$$$
Output

For each query, output a single integer on a separate line — the total number of inversions in the array after this operation.

Examples
Input
5 3
1 3 5 2 4
2 4
1 5
2 3
Output
2
7
4
Input
5 3
2 1 2 1 1
2 4
1 5
1 3
Output
5
1
5