#P9706. 排队

    ID: 6321 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-最长上升子序列耐心排序求 LIS前后缀状态分解

排队

题目描述

NN 名同学排成一列,初始位置 ii 的同学身高为 aia_i。a1,a2,…,aNa_1,a_2,\ldots,a_N 是 1,2,…,N1,2,\ldots,N 的一个排列。

老师一轮轮调整队伍。每轮按 i=1,2,…,N−1i=1,2,\ldots,N-1 的顺序比较当前位置 ii 和 i+1i+1 的两名同学。若前者更高,就立即交换两人。每轮结束后,若队伍已按身高递增排列,则停止。两名同学每次直接交换位置时,会互相分享悄悄话。

Kiana 想邀请尽可能多的同学共进午餐。受邀同学中任意两人都没有在上述调整过程中交换过悄悄话。求最大邀请人数,以及在每个达到最大人数的方案中都被邀请的同学。Kiana 自己没有参加排队,也不计入邀请人数。

输入格式

第一行一个正整数 NN。第二行 NN 个整数 a1,…,aNa_1,\ldots,a_N,为 1,2,…,N1,2,\ldots,N 的一个排列。

输出格式

第一行输出最大邀请人数。第二行按升序输出每名必定受邀的同学在初始队伍中的位置;没有必选位置时输出空行。

样例

3
3 1 2
2
2 3

数据范围

分值比例 NN 上限
10% 10
30% 300
60% 3000
100% 10510^5

原题 PDF