#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Sorting

Alice uses the following pseudocode when she needs to sort a permutation of 1 to `N` in a 1-indexed array:

procedure Sort(list A) defined as: list less, greater if length(A) <= 1 then return A pivot := A_{floor((length(A)+1) / 2)}for i := 1 to length(A) do: Increment(comparison_count) if A_{i}< pivot then append A_{i}to less else if A_{i}> pivot append A_{i}to greater end if end for return concatenate(Sort(less), pivot, Sort(greater) )

And now we are interested in the number of comparisons that will be made during the sorting of the given permutation of integers `A` with the provided code. So, we ask you to find the value of the variable `comparison_count`

after such a sorting.

### Input

The first line of input consists of a single integer `N`. The second line of input contains a permutation of the numbers 1 to `N`.

### Output

Output the number of comparisons on the first and only line of the output.

### Limits

For all testcases

- 1 ≤
`N`≤ 500000

Subtask 1 (32%): 1 ≤ `N` ≤ 2000

Subtask 2 (9%): 1 ≤ `N` ≤ 100000, the permutation is generated randomly

Subtask 3 (45%): 1 ≤ `N` ≤ 65536

Subtask 4 (14%): No additional constraints

Subtask 5 (0%): Sample

### Sample Input

5 4 3 5 1 2

### Sample Output

11

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 32 | 9 | 2.5s | 512MB | Minimum |

2 | 9 | 4 | 2.5s | 512MB | Minimum |

3 | 45 | 9 | 2.5s | 512MB | Minimum |

4 | 14 | 9 | 2.5s | 512MB | Minimum |

5 | 0 | 1 | 2.5s | 512MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o sorting_codechef -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512