#P50764. 「POI2007」堆积木 Building Blocks

「POI2007」堆积木 Building Blocks

题目描述

译自 POI 2007 Stage 3. Day 2「Klocki

Jessica 的生日礼物里有一堆积木。每个积木都是大小相同的正方体。积木上有一个数字,表示它应该处在的高度。

积木已经搭成塔,你需要从这座塔里移除积木,使得处在正确高度的积木的个数尽可能多。

输入格式

第一行一个整数 n(1n100 000)n (1 \le n \le 100\ 000),表示塔的初始高度。

接下来一行有 nn 个正整数 a1,a2,,an(1ai1 000 000)a_1, a_2, \ldots, a_n (1 \le a_i \le 1\ 000\ 000),从底部到顶部,表示积木上所写的数字。

输出格式

第一行输出一个整数 pp,表示你的方案中需要移除的积木个数,使得处在正确位置的积木个数最大。

接下来一行 pp 个正整数,表示需要移除初始塔中的积木编号。初始塔中的积木从底部到顶部按 1n1 \ldots n 编号。

样例

5
1 1 2 5 4
1
1