Problem Description

define is playing with $ N $ squares arranged horizontally. They are numbered from left to right as squares $1,\ 2,\ 3,\ ...,\ N$.
Each square $ i $ has an integer $ A_i $ written on it. The rules of the game are as follows:

• Start from square $ V_1 $ and skip to $ M $ $(M\ \geq\ 0)$ squares $V_1,\ V_2,\ V_3,\ ...,\ V_M$ in order, ending at square $ V_M $.
• You cannot move left at any point. That is, you must satisfy $1\ \leq\ V_1$.
• The points earned are calculated as |$ A_{V_2}-A_{V_1} $| $ + $ |$ A_{V_3}-A_{V_2} $| $+\ ...\ +$ |$ A_{V_M}-A_{V_{M-1}} $|.
• It is also possible not to play at all. In this case, $M\ =\ 0$ and the points are $ 0 $. Also, if only one square is visited ($M\ =\ 1$), the points are $ 0 $.

define wants to maximize his points, but he is lazy and wants to minimize the number of squares he visits.
Calculate the minimum number of squares he needs to visit on his behalf.

Input Format

The input is given from the standard input in the following format:

$ N $
$ A_1 $ $ A_2 $ $\ldots$ $ A_{N-1} $ $ A_N $

Output Format

Output a single line with the minimum number of squares that need to be visited to maximize the points.

Sample Input and Output

Sample Input #1

51 2 1 2 1

Sample Output #1

5

Sample Input #2

51 3 5 2 1

Sample Output #2

3

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ N\ \leq\ 10^5$
• $-10^9\ \leq\ A_i\ \leq\ 10^9$

Sample Explanation 1

In this case, visiting all squares gives $ 4 $ points. There is no way to get $ 4 $ points or more by visiting $ 4 $ or fewer squares.

Sample Explanation 2

In this case, visiting squares $1,\ 3,\ 5$ in order gives $ 8 $ points.

见题面 Input 部分

见题面 Output 部分