問題一覧 > 通常問題

No.284 門松と魔法(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : 紙ぺーぱー紙ぺーぱー
5 ProblemId : 662 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:43:07

問題文

かつて、kamipeipaa君の家の庭には3本しか竹はありませんでした。
今や1列に並んだ$N$本の竹からなる竹林があります。$i$番目の竹の高さは$A_i$です。

kamipeipaa君は
・竹の本数が$M(3 \le M)$本、$i$番目の竹の高さが$B_i$であるときに、$1 < i < M$について$B_{i-1}$,$B_i$,$B_{i+1}$が全て異なり、3つの要素の中で$B_i$が最大または最小
・竹が1本も存在しない。
のどちらかの条件を満たすようにしたいと考えています。
kamipeipaa君は"ある竹を1本選んで消滅させる"魔法を繰り返し使うことで、この条件を満たすようにしたいと考えています。
この条件を満たすように0本以上の竹を消滅させたとき、最大で何本の竹を残すことが可能かkamipeipaa君に教えてあげてください。

入力

$N$
$A_1$ $A_2$ ... $A_N$

1行目に竹の数を表す整数$N (1 \le N \le 10^{5})$が与えられる。
2行目に$i$番目の竹の高さを表す整数$A_i (1 \le A_i \le 10^{6})$が空白区切りで与えられる。

出力

残すことが可能な竹の数の最大値を出力せよ。

サンプル

サンプル1
入力
3
5 1 4
出力
3

魔法を使わずとも条件を満たします。

サンプル2
入力
6
4 4 4 5 1 4
出力
4

{4, 5, 1, 4}となるように魔法を使うことで、条件を満たすことが可能です。

サンプル3
入力
5
1 2 3 4 5
出力
0

全ての竹を消滅させることで条件を満たすことができます。

サンプル4
入力
2
9 3
出力
0

全ての竹を消滅させることで条件を満たすことができます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。