#P16059. [Oni2021国家队选拔赛]GP

    ID: 15270 传统题 100ms 128MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-前后缀最值排序贪心相向双指针交换论证

[Oni2021国家队选拔赛]GP

题目描述

GrandPa(简称 GP)年轻时非常喜欢算法竞赛。他参加过 NN 场重要比赛,并且每场都获得第一名、赢得一个奖杯。为了方便区分,他给这些奖杯分别编号为 11 到 NN,且任意两个不同奖杯的编号不同。

现在,这 NN 个奖杯从左到右摆在书架 AA 上。第 ii 个奖杯的编号为 PiP_i。

GP 很快要被孙辈们拜访,他想把奖杯摆得尽可能“震撼”。他会把书架 AA 上的奖杯移动到另一个初始为空的书架 BB 上。每次操作如下:

  1. 从书架 AA 中选择最左边或最右边的一个奖杯;
  2. 将这个奖杯放到书架 BB 的最左边或最右边。如果 BB 为空,则放在哪里都等价。

一直操作到书架 AA 为空、所有奖杯都被移动到书架 BB 上。

设最终书架 BB 上从左到右的编号序列为 Q1,Q2,…,QNQ_1,Q_2,\ldots,Q_N。GP 希望通过合理操作,使得序列 QQ 在所有可能得到的序列中字典序最大。

请输出这个字典序最大的序列 QQ。

输入格式

第一行一个整数 NN。

第二行 NN 个整数:

P1,P2,…,PNP_1,P_2,\ldots,P_N

表示初始书架 AA 上从左到右的奖杯编号。

输出格式

输出一行 NN 个整数:

Q1,Q2,…,QNQ_1,Q_2,\ldots,Q_N

表示能够得到的字典序最大的最终序列。

约束与说明

  • 1≤N≤1000001\le N\le 100000

  • 1≤Pi≤N1\le P_i\le N

  • 若 i≠ji\ne j,则 Pi≠PjP_i\ne P_j

  • 对于两个长度同为 KK 的序列 A,BA,B,若存在位置 pp,满足:

    • Ap>BpA_p>B_p;
    • 对所有 1≤i<p1\le i<p,都有 Ai=BiA_i=B_i;

    则称 AA 的字典序大于 BB。

子任务

子任务 分值 限制
1 6 N≤10N\le 10
2 7 N≤18N\le 18
3 25 N≤100N\le 100
4 13 N≤1000N\le 1000
5 14 P1=N−1P_1=N-1 且 PN=NP_N=N
6 35 无额外限制

样例 1

输入

4
3 2 4 1

输出

4 3 2 1

样例 2

输入

6
1 4 2 6 5 3

输出

6 5 4 3 1 2

样例 3

输入

10
9 7 8 5 1 4 2 3 6 10

输出

10 9 7 8 6 5 3 2 4 1

样例解释

样例 1 中,可以按如下方式移动:

书架 A 书架 B
3241 空
241 3
41 32
4 321
空 4321

样例 2 中,可以按如下方式移动:

书架 A 书架 B
142653 空
42653 1
4265 31
265 431
65 4312
6 54312
空 654312