Description

给出一个有N个元素的排列A，即1<=A[i]<=N，且A[i]!=A[j]。 接如下的算法执行归并排序：

Mergesort(A[], l, r, T[]){
  cnt++;
  if(A[l]~A[r]无序){
     mid = (l+r)/2;
     Mergesort(A, l, mid, T);
     Mergesort(A, mid+1, r, T);
     Merge(A, l, mid, r, T);
  }
}

在主函数中调用Mergesort(A, 1, n, T). 求这个归并排序调用总的次数cnt。

Format

Input

第1行：1个整数N，表示元素个数

第2行：N个整数表示数组元素

Output

第1行：1个整数，表示调用总次数

Samples

5
4 1 2 5 3 

9

Limitation

$1 \le N \le 10^4$