yukicoder-284

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/284 No.284 門松と魔法(2)] ==

=== Description ===

{{{
#!html
<p>有$N$棵树，第$i$棵树的高度是$A_i$。现在你需要砍掉一些树，假设剩下来树的高度为$\{B_1,B_2,\dots,B_M\}$，那么下面条件必须要满足：
<ul>
<li>$M \ge 3$</li>
<li>对于任意$1 < i < M$，$B_{i-1}, B_i, B_{i+1}$互不相同并且$B_i$要么是最大值，要么是最小值。</li>
</ul>

求最多能剩下多少树。
</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$<br>
$A_1$ $A_2$ $\dots$ $A_N$ 
</p>
<p>$1 \le N \le 10^5, 1 \le A_i \le 10^6$。</p>
}}}

=== Output ===

{{{
#!html
<p>输出最多能剩下多少树。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3
5 1 4
</pre>
}}}
输出
{{{
#!html
<pre>
3
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
6
4 4 4 5 1 4
</pre>
}}}
输出
{{{
#!html
<pre>
4
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
5
1 2 3 4 5
</pre>
}}}
输出
{{{
#!html
<pre>
0
</pre>
}}}

==== Sample 4 ====
输入
{{{
#!html
<pre>
2
9 3
</pre>
}}}
输出
{{{
#!html
<pre>
0
</pre>
}}}

No.284 門松と魔法(2)

Description

有$N$棵树，第$i$棵树的高度是$A_i$。现在你需要砍掉一些树，假设剩下来树的高度为$\{B_1,B_2,\dots,B_M\}$，那么下面条件必须要满足：

$M \ge 3$
对于任意$1 < i < M$，$B_{i-1}, B_i, B_{i+1}$互不相同并且$B_i$要么是最大值，要么是最小值。

求最多能剩下多少树。

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$

$1 \le N \le 10^5, 1 \le A_i \le 10^6$。

Output

输出最多能剩下多少树。

Sample

Sample 1

输入

35 1 4

输出

Sample 2

输入

64 4 4 5 1 4

输出

Sample 3

输入

51 2 3 4 5

输出

Sample 4

输入

29 3

输出