D - スキップ /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300

問題文

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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

ポイントを最大化するためには、最小でいくつのマスを通ればいいかを 1 行に出力せよ。


入力例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 点が得られます。

writer: define