抹平曲线

走廊丈量完了，但Zero的能量曲线是波动的——需要抹平。

"抹平？"CC问。

"对。"你说，"给定一个序列，每次可以把一个区间变成同一个值。求把整个序列变成非降的最少操作次数。"

"非降？"

"对。"你说，"每个数不大于后面的数。"

"操作？"

"对。"你说，"选一个区间，把它抹平成同一个值。"

"咋算？"

"动态规划。"你说，"$dp[i]$表示把前$i$个数变成非降的最少操作次数。"

"转移？"

"复杂。"你说，"要考虑最后一个区间的值和范围。"

"简化？"

"对。"你说，"如果只能把区间变成0或1，就是典型的DP问题。"

"第47个数。"你说，"值为47——如果要抹平，需要选一个包含它的区间。"

"区间多大？"

"看前后。"你说，"如果前面有比47大的，要一起抹平；如果后面有比47小的，也要一起。"

"像涂色？"

"对。"你说，"像涂色——一笔涂一片，颜色一样。"

"最少几笔？"

"看起伏。"你说，"起伏越多，需要的笔数越多。"

"起伏？"

"对。"你说，"上升和下降——每次转折都可能需要新的一笔。"

CC看着曲线——像心电图，像山脉，像某种有起有伏的生命。

"能抹平吗？"她问。

"能。"你说，"但会损失细节。"

"细节？"

"对。"你说，"抹平后，原来的起伏不见了。"

"好还是不好？"

"看需求。"你说，"如果需要稳定，抹平好；如果需要活力，保留好。"

Echo把抹平过程投射出来——曲线慢慢变平，像潮水退去。

"以前我太起伏。"她说，"现在……平稳了。"

"因为你找到了平衡。"你说。

"对。"她说，"因为我找到了平衡。"

题目描述

给定序列，每次操作选一个区间变成同一个值。求变成非降序列的最少操作次数。

输入格式

第一行$n$。第二行$n$个整数。

输出格式

最少操作次数。

输入样例

5
1 2 3 4 5

输出样例

0

提示

• $dp[i]$表示前$i$个数的最少操作次数。
• 考虑最后一个区间的值和右端点。
• 时间复杂度$O(n^2)$或优化到$O(n\log n)$。