笨笨的导弹攻击

笨笨的导弹攻击

测试数据来自 system/1571

背景

在那遥远的地方,有个小目标~~
笨笨:导弹准备!
路人甲:(这么小个目标都要欺负……)老大,导弹只有一部分可以用……
笨笨:不管那么多,有多少就打多少!

描述

为了彻底打击目标,笨笨要使用足够多的导弹去打击目标。

每个导弹有各自的编号,这些编号有可能重复……
现在需要将其中一部分导弹按顺序抽调出来并按原顺序排列,使得这些被抽取出来的导弹奇数位置的编号大于其前一个的编号,偶数位置的编号小于其前一个的编号,这样子才能够正常使用这些导弹攻击目标。

笨笨想知道,他最多能够正常使用多少导弹攻击目标?

格式

输入格式

第一行一个数n(0<n<=10000),表示导弹总数。

第二行n个数,按顺序表示各个导弹的编号。

输出格式

输出只有一个数,即最多能正常攻击的导弹总数。

样例1

样例输入1

4
5 3 2 4

样例输出1

3

限制

1s

来源

经典DP

信息

ID
1011
难度
9
分类
动态规划 | 动态规划 | LIS 点击显示
标签
递交数
2
已通过
2
通过率
100%
上传者