Unordered Subsequence

2000ms

262144K

Description:

The sequence is called ordered if it is non-decreasing or non-increasing. For example, sequnces [3, 1, 1, 0] and [1, 2, 3, 100] are ordered, but the sequence [1, 3, 3, 1] is not. You are given a sequence of numbers. You are to find it's shortest subsequence which is not ordered.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input:

The first line of the input contains one integer n (1 ≤ n ≤ 10⁵). The second line contains n space-separated integers — the given sequence. All numbers in this sequence do not exceed 10⁶ by absolute value.

Output:

If the given sequence does not contain any unordered subsequences, output 0. Otherwise, output the length k of the shortest such subsequence. Then output k integers from the range [1..n] — indexes of the elements of this subsequence. If there are several solutions, output any of them.

Sample Input:

5
67 499 600 42 23

Sample Output:

3
1 3 5

Sample Input:

3
1 2 3

Sample Output:

Sample Input:

3
2 3 1

Sample Output:

3
1 2 3

Informação

Provedor Codeforces

Código CF27C