Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rio and Inversion

Limits: 1s, 512 MB

One day Rio was returning home from his university and unfortunately lost his phone on the way. He asked his brother to buy him a luxurious smartphone. But his brother is not an easy person to please. He will give Rio an interesting array and some queries. If Rio can answer all the queries perfectly, only then his brother will buy him a smartphone.

The array consists of N elements. And the given queries will be of two types.
0 u v : If we swap the two elements in index u & v, what will be the number of inversions in the new array?
1 u v : If we remove the sub-array between the elements at index u and v (the elements at indexes u and v will also be removed), what will be the number of inversions in the newly formed array?

Here the number of inversion of an array A is the total number of pair of indexes (i , j) such that i < j and A[i] > A[j]. And of course (0 <= i < j < N).

Rio was stuck in this problem for few days and could not figure out how to solve this. But he really needs a phone now. As one of his best friends, can you help him?

Input

First line contains a single element N. In the next line there will be N (1 <= N <= 104) integers. For all the values of Ai the limit will be (0 <= Ai < 100). In the next line, there will be an integer Q (1 <= Q <= 104). Then from next line there will be Q queries of the given types 0 or 1.

All the queries will be zero based indexed and (0 <= u,v < N).

Changes made in a query are temporary. They will not affect the queries that come after it. After each query, the array will revert back to its initial form.

Output

For each of the query, print the number of inversions in a single line.

Samples

InputOutput
12
3 8 2 5 12 1 7 14 9 5 3 8
10
1 8 11
1 2 5
1 6 9
1 3 8
1 6 6
0 8 11
0 2 5
0 6 9
0 3 8
0 6 6
10
13
12
5
23
26
26
26
30
27

Note that there is no update operation for the array elements. Array will always be fixed to its original configuration after a query has been performed.

Author
  • flash_7's Avatar

    flash_7

    Tarango works NSUPS. He loves to play FIFA & travel with friends. When not solving problems, he spends most of his time day dreaming. And, he most definitely is not a "manga lover".
Discussion
Submit

Login to submit