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.

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

提交代码