define君は、横に並んだ N 個のマス目で遊んでいます。左から順に、マス 1, 2, 3, ..., N と番号付けられています。
マス i には、整数A_iが書かれています。遊び方は、次の通りです。

• マス V_1 からスタートし、スキップで M (M \geq 0) 箇所のマス V_1, V_2, V_3, ..., V_M を順に経由し、マス V_M でゴールする。
• 途中で左に進んでは行けない。すなわち、1 \leq V_1 < V_2 < V_3 < ... < V_M \leq N を満たす必要がある。
• この時のポイントは |A_{V_2}-A_{V_1}| + |A_{V_3}-A_{V_2}| + ... + |A_{V_M}-A_{V_{M-1}}| 点となる。
• なお、遊ばないという選択もできる。この場合 M = 0 となり、ポイントは 0 点となる。また、1 箇所しか経由しない場合 (M = 1 の場合) も 0 点となる。

さて、define君はポイントを最大化したいと考えていますが、彼は面倒くさがりなのでなるべく経由するマスの個数を少なくしたいです。
彼の代わりに、経由するマスの個数の最小値を計算してあげてください。

制約

• 入力は全て整数である。
• 1 \leq N \leq 10^5
• -10^9 \leq A_i \leq 10^9

入力例1

5
1 2 1 2 1

出力例1

5

この場合、全てのマスを通ると、ポイントが 4 点になります。
通るマスが 4 カ所以下でポイントを 4 点以上にする遊び方はありません。

入力例2

5
1 3 5 2 1

出力例2

3

この場合は、マス 1, 3, 5 を順に通ると 8 点が得られます。