You are given an array of ~N~ integers. Your task is to output one valid Longest Increasing Subsequence (LIS).

A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements. A subsequence is increasing if every next element is strictly larger than the previous one.

Input Format

The first line contains a single integer ~N~.

The second line contains ~N~ integers ~a_1, a_2, ..., a_N~.

Output Format

Print:

• on the first line, the length of the LIS
• on the second line, the indices of one valid LIS in increasing order

Indices are ~1~-based.

Example

Input

8
7 3 5 3 6 2 9 8

Output

4
2 3 5 7

Explanation

The values at indices ~2, 3, 5, 7~ are ~3, 5, 6, 9~, which form a longest increasing subsequence.

Constraints

• ~1 ≤ N ≤ 200000~
• ~1 ≤ a_i ≤ 10^9~

Subtasks

• 60% of the tests satisfy ~N ≤ 5000~. An ~O(N^2)~ solution is accepted here.
• 40% of the tests use the full constraints and require an ~O(N \log N)~ solution.