BST Insertion Cost

Given a permutation \(a\) of \(1\) to \(n\), insert the elements one by one into a Binary Search Tree (BST). The first number is already set as the root of the BST. The insertion is performed using the following pseudocode:

insert(number x, node n)
    c + 1;
    if x is less than the number in node n
        if n has no left child
            create a new node with the number x and set it as the left child of node n
        else
            insert(x, left child of node n)
    else (i.e. if x is greater than the number in node n)
        if n has no right child
            create a new node with the number x and set it as the right child of node n
        else
            insert(x, right child of node n)

Your task is to calculate the total number of times the insertion function executes a step (i.e. the number of times c is incremented) over all insertions.

Note: The first number is already the BST root and is not inserted using the insert function.

inputFormat

The first line contains an integer \(n\) (the size of the permutation).
The second line contains \(n\) space-separated integers representing a permutation of \(1\) to \(n\).

outputFormat

Output a single integer, which is the total number of times the insertion function increments \(c\) when inserting all elements (except the first one which is the root).

sample

3
3 2 1

3