SUPPER - Supernumbers in a permutation

An n-element permutation is an n-element sequence of distinct numbers from the set {1, 2, ... n}. For example the sequence 2, 1, 4, 5, 3 is a 5-element 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 n-element 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

Added by:Adam Dzedzej
Date:2004-06-10
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

hide comments
2018-05-24 15:37:40
@Saptarshi, optimize your code :)
2017-11-07 06:27:14
for 5 4 3 2 1 all of them would be supernumbers! right?
2017-07-09 11:43:34
how to get input???
do we have to get 10 test cases or we can get less than 10 test case?????
2015-12-30 17:28:29 kejriwal
Awesome Problem :)
2015-06-19 22:31:27 Ankit Sultana
Damn. This has to be my best guess ever. Proving the algorithm's correctness was really nice !
2013-06-27 18:19:13 Aditya Gourav
grt problem, njoyed doing it :)
2012-10-09 19:08:25 Saptarshi Chatterjee
@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 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.