题目背景

本题测试数据不保证正确。

题目描述

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

输入格式

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

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

输出格式

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

4
1 3 16 17

2

提示

样例说明

其中一种方案：在 $6, 10$ 处插入两名同学，新队伍为 $1, 3, 6, 10, 16, 17$，满足条件。

评测用例规模与约定

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