#CODEFORCESP7348. Company Income Growth
Company Income Growth
Company Income Growth
题面翻译
题目描述
给出一个长度为的序列,求一个最长的递增序列,设其长度为,则有
输入格式
第一行一个正整数表示序列长度
第二行个整数
输出格式
第一行一个非负整数表示的长度
接下来个正整数描述序列
题目描述
Petya works as a PR manager for a successful Berland company BerSoft. He needs to prepare a presentation on the company income growth since (the year of its founding) till now. Petya knows that in the company income amounted to billion bourles, in — to billion, ..., and in the current -th year — billion bourles. On the base of the information Petya decided to show in his presentation the linear progress history which is in his opinion perfect. According to a graph Petya has already made, in the first year BerSoft company income must amount to billion bourles, in the second year — billion bourles etc., each following year the income increases by billion bourles. Unfortunately, the real numbers are different from the perfect ones. Among the numbers can even occur negative ones that are a sign of the company’s losses in some years. That is why Petya wants to ignore some data, in other words, cross some numbers from the sequence and leave only some subsequence that has perfect growth.
Thus Petya has to choose a sequence of years , , ..., ,so that in the year the company income amounted to billion bourles, in the year — billion bourles etc., in accordance with the perfect growth dynamics. Help him to choose the longest such sequence.
输入格式
The first line contains an integer ( ). The next line contains integers ( ). The number determines the income of BerSoft company in the -th year. The numbers in the line are separated by spaces.
输出格式
Output — the maximum possible length of a perfect sequence. In the next line output the sequence of years , , ..., . Separate the numbers by spaces. If the answer is not unique, output any. If no solution exist, output one number .
样例 #1
样例输入 #1
10
-2 1 1 3 2 3 4 -10 -2 5
样例输出 #1
5
2002 2005 2006 2007 2010
样例 #2
样例输入 #2
3
-1 -2 -3
样例输出 #2
0