排练
题号：NC309356
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小蓝的班上有 n 名同学正在为校庆活动排练节目，他们在舞台上站成一排。若把他们看做在数轴上，从左到右第 i 名同学的位置即为 a_i。为了美观，小蓝想在队伍中插入一些新同学，使得在新队伍中，对于任意三名相邻的同学的位置 a_{i-1}, a_i, a_{i+1} 满足 a_{i+1} - a_i \le 2(a_i - a_{i-1})。小蓝想知道最少增加多少名同学可以满足条件。

输入描述:

输入的第一行包含一个正整数 n。

第二行包含 n 个正整数 a_1, a_2, \cdots, a_n，相邻整数之间使用一个空格分隔。

输出描述:

输出一行包含一个整数表示答案。
示例1

输入

复制 
4
1 3 16 17

输出

复制 
2

说明

其中一种方案：在 6, 10 处插入两名同学，新队伍为 1, 3, 6, 10, 16, 17，满足条件。
(3-1=2, 6-3=3<=4, 10-6=4<=6, 16-10=6<=8, 17-16=1<=12)

备注:

- 对于 20% 的评测用例，1 \le n \le 10^3；
- 对于所有评测用例，1 \le n \le 10^5, 1 \le a_i \le 10^8, a_{i+1} > a_i。