Bubble sort is an algorithm to sort a sequence. Let's say we are going to sort a sequence of length in non-decreasing order. Bubble sort swaps two adjacent numbers when they are not in the correct order. Swaps are done by repeatedly passing through the sequence. Precisely speaking, in a **pass**, we swap and if , for in this order. It is known that any sequence can be sorted in non-decreasing order by some passes. For a sequence , we define the **number of passes by bubble sort** as the number of passes needed to sort using the above algorithm.

JOI-kun has a sequence of length . He is going to process queries of modifying values of . To be specific, in the ()-th query (), the value of is changed into .

JOI-kun wants to know the number of passes by bubble sort for the sequence after processing each query.

#### Example

Given a sequence of length and queries: , .

- For the first query, the value of is changed into . We obtain .
- For the second query, the value of is changed into . We obtain .

Bubble sort for :

- is not sorted, so the first pass starts. Since , we swap them to get . Since , we don't swap them. Since , we don't swap them.
- Now is sorted, so the bubble sort ends.

Hence, the number of passes by bubble sort is for .

Bubble sort for :

- is not sorted, so the first pass starts. Since , we swap them to get . Since , we swap them to get . Since , we don't swap them.
- is not sorted yet, so the second pass starts. Since , we swap them to get . Since , we don't swap them. Since , we don't swap them.
- Now is sorted, so the bubble sort ends.

Hence, then number of passes by bubble sort is for .

#### Subtasks

There are 4 subtasks. The score and the constraints for each subtask are as follows:

Subtask | Score | |||
---|---|---|---|---|

1 | 17 | |||

2 | 21 | |||

3 | 22 | |||

4 | 40 |

#### Implementation details

You should implement the following function `countScans`

to answer queries.

```
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
```

`A`

: array of integers of length representing the initial values of the sequence.`X, V`

: arrays of integers of length representing queries.- This function should return an array of integers of length . For each , should be the number of passes by bubble sort for the sequence right after processing ()-th query.

## Comments