H. Home Workout Playlist
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Life feels dull when you cannot go outside or meet your favorite people. Fortunately, your favorite bands keep releasing new hits this year, such as Ussewa, Wan Koei Tuen, and Thought Crime. Therefore, you decide to work out at home with your playlist!

You have a playlist of $$$N$$$ songs, numbered from $$$1$$$ to $$$N$$$, representing the order in which they are played. Each song $$$i$$$ has a hypeness value $$$A_i$$$.

While exercising, you only want to listen to songs that match a certain pattern of rising excitement. You may choose to skip some songs, keeping the remaining ones in their original order.

Formally, let $$$S = [S_1, S_2, \dots, S_k]$$$ be a subsequence of $$$[1, 2, \dots, N]$$$ representing the indices of unskipped songs. Your task is to find the longest possible subsequence $$$S$$$ such that:

  • The hypeness strictly increases: $$$A_{S_i} \gt A_{S_{i-1}}$$$ for all $$$i \ge 2$$$.
  • The increase in hypeness also strictly increases: $$$A_{S_i} - A_{S_{i-1}} \gt A_{S_{i-1}} - A_{S_{i-2}}$$$ for all $$$i \ge 3$$$.

In other words, both the hypeness values and the gaps between them must form strictly increasing sequences. Find the maximum possible length of such a subsequence $$$S$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 5 \cdot 10^4$$$) — the number of songs in the playlist.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^5$$$) — the hypeness values of the songs.

Output

On the first line, print one integer $$$k$$$ — the number of unskipped songs.

On the second line, print $$$k$$$ integers — the indices of the unskipped songs in ascending order.

If there are multiple valid lists of unskipped songs, you may print any of them.

Example
Input
5
2 1 3 4 6
Output
3
3 4 5
Note

Other valid lists of unskipped songs include $$$[1, 3, 5]$$$, which correspond to hypeness values $$$[2, 3, 6]$$$, and $$$[2, 3, 5]$$$, which correspond to hypeness values $$$[1, 3, 6]$$$. You may output any of them.