SUPPER  Supernumbers in a permutation
An nelement permutation is an nelement sequence of distinct numbers from the set {1, 2, ...,n}. For example the sequence 2,1,4,5,3 is a 5element permutation. We are interested in the longest increasing subsequences in a permutation. In this exemplary permutation they are of length 3 and there are exactly 2 such subsequences: 2,4,5 and 1,4,5. We will call a number belonging to any of the longest increasing subsequences a supernumber. In the permutation 2,1,4,5,3 the supernumbers are 1,2,4,5 and 3 is not a supernumber. Your task is to find all supernumbers for a given permutation.
Task
Write a program which
 reads a permutation from standard input,
 finds all its supernumbers,
 writes all found numbers to standard output.
Input
Ten test cases (given one under another, you have to process all!). Each test case consists of two lines. In the first line there is a number n (1<=n<=100000). In the second line: an nelement permutation  n numbers separated by single spaces.
Output
For every test case your program should write two lines. In the first line  the number of supernumbers in the input permutation. In the second line the supernumbers separated by single spaces in increasing order.
Example
Input: 5 2 1 4 5 3 [and 9 test cases more] Output: 4 1 2 4 5 [and 9 test cases more]Warning: large Input/Output data, be careful with certain languages
hide comments
zakir068:
20200226 06:11:33
LIS


l1356355470:
20181216 07:32:43
Oh，Wrong Answer 

ndrewxie:
20180524 15:37:40
@Saptarshi, optimize your code :) 

mudra03:
20171107 06:27:14
for 5 4 3 2 1 all of them would be supernumbers! right? 

poorya:
20170709 11:43:34
how to get input???


kejriwal:
20151230 17:28:29
Awesome Problem :) 

Ankit Sultana:
20150619 22:31:27
Damn. This has to be my best guess ever. Proving the algorithm's correctness was really nice ! 

Aditya Gourav:
20130627 18:19:13
grt problem, njoyed doing it :) 

Saptarshi Chatterjee:
20121009 19:08:25
@moderator  I see no accepted solution for this in ruby , I have O(nlogn) complexity for my code and gettingg TLE .Can you please check the time limit for ruby ? 
Added by:  Adam Dzedzej 
Date:  20040610 
Time limit:  2.25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Internet Contest Pogromcy Algorytmow (Algorithm Tamers) Round IV, 2003 