CF BUDDY
← Problems·

27C · Unordered Subsequence

1900 · constructive algorithms, greedy

Problem: 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 Format: The first line of the input contains one integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers — the given sequence. All numbers in this sequence do not exceed 106 by absolute value.

Output Format: 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 Cases

Case 1

Input

5
67 499 600 42 23

Output

3
1 3 5

Case 2

Input

3
1 2 3

Output

0

Case 3

Input

3
2 3 1

Output

3
1 2 3

Similar problems

00:00:00
Loading editor…
Welcome! I'm your coding tutor for this problem. Use the chips below to reveal stored hints or get AI feedback on your code. I'll guide you step by step — never giving away the solution.

Sign in to unlock AI tutor feedback