0066. Nice Subsequence

Имя входного файла:	subseq.in
Имя выходного файла:	subseq.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

Let us call some sequence of positive integer numbers {\em nice} if for each i either a_i = 1 or the quantity of such j < i that a_j = a_i - 1 is greater than the quantity of such j < i that a_j = a_i.

You are given a sequence of positive integer numbers and your task is to find its longest nice subsequence.

Input file

The first line of the input file contains N – the number of elements in the sequence you are given (1 ≤ N ≤ 100,000). N positive integer numbers a₁, a₂, …, a_N follow, separated by spaces and/or line feeds.

Output file

First output L – the number of elements in the subsequence found. After that output L integer numbers 1 ≤ i₁ < i₂ < … < i_L ≤ N, such that a_i1, a_i2, …, a_iL is the nice subsequence found.

Examples:

subseq.in	subseq.out
10 2 3 1 3 2 1 2 2 4 3	5 3 5 6 7 10

Источник: Petrozavodsk Winter 2003. St. Petersburg Contest I

Обсудить       Отправить решение



Версия для печати