Sorting

Alice uses the following pseudocode when she needs to sort a permutation of Npositive integers:

procedure Sort(list A) defined as: 
   list less, greater
   if length(A) <= 1 then return A
   pivot := A_{(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 N numbers.

Output

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

Example

Input:
5
4 3 5 1 2

Output:
11

Solution

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <limits.h>

int comparison_count;

void debug_array(int *array, int array_size) {
    printf("\n");
    printf("[");
    int i;
    for (i = 0; i < array_size; i++) {
        printf("%3d", array[i]);
    }
    printf("]");
    printf("\n");
}

unsigned long long bigrand() {
    unsigned long long big_rand = 0;
    big_rand = rand();
    big_rand = big_rand << 32;
    big_rand |= rand();
    return big_rand;
}

int randint(int start_range, int end_range) {
    return  (bigrand() % ((end_range + 1) - start_range)) + start_range;
}

void concatenate(int *concatenated,
                 int concatenated_size,
                 int *less,
                 int less_size,
                 int pivot,
                 int *greater,
                 int greater_size) {
    int concatenated_idx = 0;
    int i;
    for (i = 0; i < less_size; i++) {
        concatenated[concatenated_idx++] = less[i];
    }
    concatenated[concatenated_idx++] = pivot;
    for (i = 0; i < greater_size; i++) {
        concatenated[concatenated_idx++] = greater[i];
    }
}

int *sort(int *array, int array_size) {
    if (array_size <= 1) {
        return array;
    }
    int pivot = array[(array_size - 1) / 2];
    int *less = calloc(array_size, sizeof(int));
    int less_idx = 0;
    int *greater = calloc(array_size, sizeof(int));
    int greater_idx = 0;
    memset(less, -1, array_size * sizeof(int));
    memset(greater, -1, array_size * sizeof(int));
    int i;
    for (i = 0; i < array_size; i++) {
        comparison_count++;
        if(array[i] < pivot) {
            less[less_idx++] = array[i];
        } else if (array[i] > pivot) {
            greater[greater_idx++] = array[i];
        }
    }
    
    int concatenated_size = less_idx + greater_idx + 1;
    int *concatenated = calloc(concatenated_size, sizeof(int));
    concatenate(concatenated,
                concatenated_size,
                sort(less, less_idx),
                less_idx,
                pivot,
                sort(greater, greater_idx),
                greater_idx);
    return concatenated;
}

float calc_elapsed_time(clock_t time_s, clock_t time_e) {
    return (((float)time_e - (float)time_s) / CLOCKS_PER_SEC) * 1000;
}

int main(int argc, const char * argv[])
{
    
    int N;
    scanf("%d", &N);
    int *A = calloc(N, sizeof(int));
    int i;
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    comparison_count = 0;
    
    int *sorted = sort(A, N);
    free(sorted);
    
    
    printf("%d\n", comparison_count);
    return 0;
}