Rio and Inversion

flash_7 Intra RUET Individual Con...
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.

Sample

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.

Submit

Login to submit.

Statistics

86% Solution Ratio
bqi343Earliest, Jul '16
QuwsarOhiFastest, 0.0s
shefinLightest, 262 kB
Deshi_TouristShortest, 755B
Toph uses cookies. By continuing you agree to our Cookie Policy.