Unordered Subsequence (Codeforces 27C)
Tags: Greedy, constructive algorithms

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 ≤ 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: 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 Inputs:
5
67 499 600 42 23

3
1 2 3

3
2 3 1

Sample Outputs:
3
1 3 5

0

3
1 2 3

Solution (Python):
def main():
    n = int(input())
    seq = tuple(map(int, input().split()))
    if n < 3:
        print(0)
        return
    (a, b) = (0, 1)
    while seq[b] == seq[a] and b < n - 1:
        b += 1
    for i in range(b + 1, n):
        if seq[i] == seq[b]:
            continue
        if seq[a] < seq[b] < seq[i] or seq[a] > seq[b] > seq[i]:
            (a, b) = (b, i)
        else:
            print(3)
            print(a + 1, b + 1, i + 1)
            break
    else:
        print(0)
if __name__ == '__main__':
    main()

Solution (Python):
input()
a = list(map(int, input().split()))
p = 0
f = 1
try:
    while 1:
        if a[p] > a[p + 1]:
            q = p + 1
            while 1:
                if a[q] < a[q + 1]:
                    print(3)
                    print(p + 1, q + 1, q + 2)
                    f = 0
                    exit()
                else:
                    q += 1
        elif a[p] < a[p + 1]:
            q = p + 1
            while 1:
                if a[q] > a[q + 1]:
                    print(3)
                    print(p + 1, q + 1, q + 2)
                    f = 0
                    exit()
                else:
                    q += 1
        else:
            p += 1
except:
    if f:
        print(0)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(2, n):
    if (a[i] - a[i - 1]) * (a[i - 1] - a[0]) < 0:
        print(3, 1, i, i + 1)
        exit()
print(0)