You know, it is absolutely unimportant for us what language one uses. We quit that game long ago. Basic, Pascal, C++ or Java - it is up to a programmer himself to choose. Just do not deprive us of this option. We want to show our deprecation for ACM ICPC managers who dropped Pascal as an official programming language of this championship. This problem is dedicated to everyone who is responsible for such a strange decision.
Programmer Andrew Drinker took a sip of kvass and reclined on the back of a stool. Certainly, the stool did not have any back at all, so there was nothing surprising about Andrew, who fell to the floor cursing desperately escorted by the kvass bottle and the stool. But even such a miserable event - so much kvass was wasted! - could not spoil famous programmer's elated mood. After all, he had just completed the last version of the program which had to prove C++ as the best programming language ever been and Intel C++ Compiler as the fastest compiler in universe. "The problem is finally solved... My O(N^5) algo is supreme... Pascal must die...", - such thoughts volleyed through a mind of Mr. Drinker, whereas he was looking out over a panorama of his home city Tmutarakan through a dirty window sipping the remnant of kvass...
At that very moment in faraway Mexico programmer Pedro Gomes grinned contentedly while drinking the next bottle of maté in the attic of his shanty. Several minutes ago he had finished the main program of his life, which was predestined to establish a total domination of the legendary programming language Pascal and the world best compiler AMD Pascal Compiler - from here to eternity! "The time has come... O(N^5) is unbeatable... C++ must die...", - a mighty brain of Mr. Gomes was overfilled by wise thoughts...
Now you must be interested in what problem was solved by Andrew and Pedro, and why did their solutions get TLE on the 6-th test?
A sequence S consists of N elements S[i] indexed from 1 to N. You should take a maximal number of different elements from this sequence which are successive terms of some increasing arithmetical progression. The order of these elements in the sequence S does not matter. And may Pascal (or C++?) be with you.
The first line contains the integer N (2 ≤ N ≤ 2000). The second line contains N integers S[i] (0 ≤ S[i] ≤ 109).
The first line should contain the maximal number of taken elements. The second line should contain the indexes of these elements in the sequence S. The indexes may be listed in any order and should be separated by single spaces. If the problem has several solutions, you should output any of them.
7 3 2 3 5 9
4 5 1 6
Your solution must be really fast to pass the time-limit.
If your solution works faster than 0.1 sec. and uses less than 1 Mb. of memory, we recommend you to pay attention to the problem "Pascal vs. C++. Version 2"
Problem Author: Ilya Grebnov, Dmitry Kovalioff, Nikita Rybak
Problem Source: Timus Top Coders: Second Challenge