传统题 1000ms 256MiB

拔萝卜啦(easy)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

elioingelioing非常喜欢拔萝卜,有一天他找萝卜走进了一片魔法萝卜田,发现这里有很多的萝卜,但是这里面的萝卜都被一个邪恶的女巫 hmxhmx 施加了魔法……为了打败邪恶的女巫,请你帮帮 elioingelioing!

题目描述

elioelio 发现了一种破除魔法的办法,他发现在萝卜田的最前方有一排树,每棵树上都有一个数字,那是女巫的魔法印记,每个印记都是一个不同的数字,从左到右的位置记为 aia_i ,如果同时满足以下条件

存在 i,ji,j 使得 i>ji>j,并且 ai<aja_i<a_j

那么只要同时按下俩个树的按钮,就可以拔出一个萝卜了。elioelio 找来了他的小狗 lmzlmz,帮他一起按按钮,请你计算一下,最多可以拔到多少根萝卜?(保证这 nn 个数是一个排列)

输入格式

第一行输入一个数字 nn

第二行的输入 nn 个数字表示 aia_i

输出格式

输出一个整数数表示答案

样例

3
3 2 1
3
6
1 6 2 3 5 4
5

限制与提示

1n2×1051\leq n \leq 2\times 10^5 , 1ain1\leq a_i \leq n 保证aia_i各不相同

2026 XAUT 西安理工大学新生赛-同步赛 & XJSACM Round 1

未参加
状态
已结束
规则
ACM/ICPC
题目
15
开始于
2026-1-11 13:00
结束于
2026-1-11 18:00
持续时间
5 小时
主持人
参赛人数
6