Inserting Students for Aesthetic Arrangement

There are n students standing in a row on the stage for the school celebration. Their positions on the number line are given by \(a_1, a_2, \dots, a_n\) from left to right. In order to make the arrangement look more aesthetic, Xiao Lan wishes to insert some new students between the existing ones. The final lineup (which includes both the original and inserted students) must satisfy the following property:

For any three consecutive students with positions \(a_{i-1}\), \(a_i\), and \(a_{i+1}\), it must hold that \[ a_{i+1} - a_i \le 2\bigl(a_i - a_{i-1}\bigr). \]

Your task is to compute the minimum number of students that need to be added so that the final lineup satisfies the condition. Note that the original students remain in their initial order and you can insert the new students anywhere between them.

Hint: The only potential violations of the property occur in the triples that involve two adjacent original students (with no inserted student in between) and the next original student. For each such triple \((a_{i-1}, a_i, a_{i+1})\) (with \(2\le i\le n-1\)), let \(L = a_i - a_{i-1}\) and \(g = a_{i+1} - a_i\). If \(g \le 2L\) the condition is satisfied; otherwise, you need to insert a minimum number of students between \(a_i\) and \(a_{i+1}\) such that when the gap \(g\) is broken into \(m+1\) segments \(d_1,d_2,\dots,d_{m+1}\) the following holds: \[ d_1 \le 2L,\quad d_2 \le 2d_1,\quad d_3 \le 2d_2,\quad \dots,\quad d_{m+1} \le 2d_m. \] It can be shown that the maximum total gap that can be adjusted with m inserted students is \[ 2L \times (2^{m+1}-1). \] Thus, for each gap \(g\) between adjacent original students (except the very first gap) you must choose the minimum nonnegative integer \(m\) such that \[ 2L\times (2^{m+1}-1) \ge g. \] The final answer is the sum of such \(m\) values over every applicable gap.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of original students. The second line contains n space‐separated integers \(a_1, a_2, \dots, a_n\) (1 ≤ a_i ≤ 10⁹) representing the positions of the students in order from left to right.

outputFormat

Output a single integer, which is the minimum number of students that need to be inserted.

sample

3
1 3 8

1