CodeForces - 27C Unordered Subsequence（暴力模拟）-蒲公英云

CodeForces - 27C Unordered Subsequence（暴力模拟）

男娘i 2022-06-09 00:12 281阅读 0赞

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 kintegers from the range [1..n] — indexes of the elements of this subsequence. If there are several solutions, output any of them.

Example

Input

5
67 499 600 42 23

Output

3
1 3 5

Input

3
1 2 3

Output

Input

3
2 3 1

Output

3
1 2 3

题解：

给一个序列，让你找一个最短的大小大的组合或者小大小的组合，输出选择的位位置

思路：

最短的话也就只有3位了，模拟一下加点判断就好了，因为是输出任意一组，那么我们就从1开始找一组就行了

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
using namespace std;
#define lson k*2
#define rson k*2+1
#define M (t[k].l+t[k].r)/2
#define INF 1008611111
#define ll long long
#define eps 1e-15
int a[100005];
int main()
{
    int n,i,j,flag=0,tag,x;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    if(n<3)//小3不存在
    {
        printf("0\n");
        return 0;
    }
    i=1;
    while(a[0]==a[i]&&i<n)//找到第一个与首个值不同的下标
        i++;
    int q,w;
    if(a[i]>a[0])//如果是个小大小组合
    {
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[j-1])//找到一个转折点
            {
                q=j;
                w=j+1;
                flag=1;
                break;
            }
        }
    }
    else//大小大组合
    {
        for(j=i+1;j<n;j++)
        {
            if(a[j]>a[j-1])//同理找一个转折点
            {
                q=j;
                w=j+1;
                flag=1;
                break;
            }
        }
    }
    if(!flag)
        printf("0\n");
    else
    {
        printf("3\n");
        printf("%d %d %d\n",1,q,w);
    }
    return 0;
}