Magical Bamboo Cutting

Little Ming is cutting bamboo. In front of him are \(n\) bamboo stalks arranged in a row, where the height of the \(i\)-th bamboo is \(h_i\) initially. He finds that cutting one bamboo at a time is too slow so he decides to use magic.

The magic can be applied to any contiguous segment of bamboos that all have the same height, say \(H\). One use of the magic will change the height of every bamboo in that segment to \[ \left\lfloor \sqrt{\left\lfloor \frac{H}{2} \right\rfloor +1} \right\rfloor, \] where \(\lfloor x\rfloor\) denotes the floor of \(x\). Little Ming wants to know the minimum number of magic operations needed so that all bamboos become of height 1.

Note: An operation can only be applied on a contiguous segment if all bamboos in that segment have the same height greater than 1. Also, after an operation, adjacent segments with equal heights are automatically merged.

Example: If a bamboo’s current height is 6 then applying magic will change its height to \(\left\lfloor\sqrt{\lfloor6/2\rfloor+1}\right\rfloor = \left\lfloor \sqrt{3+1} \right\rfloor = 2\), and if its height is 2 then it becomes \(\left\lfloor\sqrt{\lfloor2/2\rfloor+1}\right\rfloor = \left\lfloor \sqrt{1+1} \right\rfloor = 1\>.

inputFormat

The first line contains a single integer \(n\) representing the number of bamboo stalks.

The second line contains \(n\) integers \(h_1, h_2, \dots, h_n\) representing the initial heights of the bamboo stalks.

outputFormat

Output a single integer: the minimum number of magic operations needed to make all bamboo heights equal to 1.

sample

1
1

0