#B. 论整齐度与美观

    传统题 5000ms 16~512MiB

论整齐度与美观

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

题目描述

玻璃管内有 nn 个小球,编号为 1n1\sim n,从左往右第 ii 颗球编号为 pip_i

接下来你每次从管左边或右边取出一个球,直到把所有球取完,设你第 ii 次取到的球编号为 qiq_i

称满足 i<j<k,qi<qj<qki<j<k,q_i<q_j<q_k 的三元组 (i,j,k)(i,j,k) 数量为 qq 的整齐度。当然,根据题目《论整齐度与美观》,你需要求出 qq 的最小整齐度。

输入格式

输入的第一行有一个正整数 nn

第二行有 nn 个正整数 p1,p2,,pnp_1,p_2,\ldots,p_n,其中 1n1\sim n 各出现一次。

输出格式

输出一行一个自然数,表示最小整齐度。

样例 #1

样例输入 #1

7
1 5 7 4 3 2 6

样例输出 #1

1

样例 #2, #3

点我下载大样例

两个样例分别满足测试点 6,206,20 的限制。

提示

【样例解释】

按照 6,1,5,7,4,3,26,1,5,7,4,3,2 的顺序取,只有 q2<q3<q4q_2<q_3<q_4 是整齐的,所以输出 11

可以证明没有整齐度更小的方案,但是方案是否唯一,我不知道。

【数据规模】

Testcases nn\le 特殊性质 空间限制
131\sim 3 1616 512MB512MB
454\sim 5 4040
686\sim 8 500500
99 5×1035\times 10^3 A
101410\sim 14
151615\sim 16 2×1032\times 10^3 16MB16MB
172017\sim 20 2×1042\times 10^4
  • 性质 A:存在 xx 使得 p1,p2,,pxp_1,p_2,\ldots,p_x 单调递减,px,px+1,,pnp_x,p_{x+1},\ldots,p_{n} 单调递增。

对于全部数据,保证 3n2×1043\le n\le 2\times 10^4

[YDRG#003 Div. 1] YDSP-S 组赛前模拟 · 云斗杯十月 Golden Round

已参加
状态
已结束 (已参加)
规则
OI
题目
6
开始于
2023-10-14 8:30
结束于
2023-10-14 13:30
持续时间
5 小时
主持人
参赛人数
287