B. Cocktail Sort
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Andrew has just learned about cocktail sort and has developed the following C++ code: 

bool comp(int x, int y) {
    return x > y;
}
void sort(vector<int> &arr) {
    int n = arr.size();
    for(int iter = 0; iter < n-1; iter = iter + 1) {
        bool done_sorting = true;
        for(int i = 0; i < n-1; i = i + 1) {
            if(comp(arr[i], arr[i+1])) {
                done_sorting = false;
                swap(arr[i], arr[i+1]);
            }
        }

        for(int i = n-1; i > 0; i = i - 1) {
            if(comp(arr[i-1], arr[i])) {
                done_sorting = false;
                swap(arr[i-1], arr[i]);
            }
        }
        
        if(done_sorting) break;
    }

}

Andrew claims that this sorting algorithm is such a significant optimization to bubble sort, so it must have a time complexity of $$$O(n)$$$. To prove the foolishness of this claim, Ben created some arrays that might still take a large number of operations to sort the array. However, these cases are too big for Andrew to analyze, so he has asked you to write a program to count the total number of operations needed for this code to sort a given array. Andrew has defined an operation as a call to the "comp" or the "swap" functions.

Input

The first line of input consists of one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the size of the array.

The second line of input consists of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... , $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

Output

Output a single integer — the number of operations needed to sort the array.

Examples
Input
9
3 1 4 1 5 9 2 6 5
Output
58
Input
7
2 7 1 8 2 8 1
Output
45
Input
4
1 6 1 8
Output
13