Special Tower of Hanoi

Natsuzora is playing a variant of the Tower of Hanoi. There are three rods: A, B, and C. Initially, n disks of distinct sizes are stacked in an arbitrary order on rod A (the first number given represents the top disk), while rods B and C are empty. The disks can be moved between rods subject to the following rules:

• Only one disk may be moved at a time; only the top disk of a rod can be moved.
• When placing a disk onto rod B or rod C, if the rod is non-empty, the disk being moved must be smaller than the disk currently on top. In other words, on rods B and C it is forbidden to place a disk onto a disk that is smaller than it.
• On rod A, there is no restriction – a larger disk may be placed on a smaller one.

The goal is to move all disks from rod A to rod B while obeying the rules above. Under these conditions, determine the minimum number of moves required to achieve this goal.

Hint: Let \( k \) be the length of the longest contiguous sequence from the top of rod A that is already in strictly descending order (i.e. for disks a₁, a₂, \(\ldots\), a_k, we have \(a_1 > a_2 > \cdots > a_k\)). It can be shown that the minimum number of moves is given by:

[ \text{moves} = 2\times (n - k) + k. ]

For example, if n = 2 and the disks on rod A (from top to bottom) are [1, 2], then \( k = 1 \) (since 1 is not greater than 2) and the minimum number of moves is \(2\times(2-1)+1=3\). In contrast, if the disks are [2, 1], then \( k = 2 \) and the answer is 2.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of disks.

The second line contains n space‐separated integers representing the sizes of the disks in the order they are stacked on rod A, with the first number being the top disk.

outputFormat

Output a single integer – the minimum number of moves required to move all disks from rod A to rod B under the given rules.

sample

2
2 1

2