Problem Unsorting Array

Link: http://codeforces.com/problemset/problem/252/B

B. Unsorting Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Petya likes arrays of integers a lot. Recently his mother has presented him one such array consisting of n elements. Petya is now wondering whether he can swap any two distinct integers in the array so that the array got unsorted. Please note that Petya can not swap equal integers even if they are in distinct positions in the array. Also note that Petya must swap some two integers even if the original array meets all requirements.

Array a (the array elements are indexed from 1) consisting of n elements is called sorted if it meets at least one of the following two conditions:

1. a₁ ≤ a₂ ≤ ... ≤ a_n;
2. a₁ ≥ a₂ ≥ ... ≥ a_n.

Help Petya find the two required positions to swap or else say that they do not exist.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁵). The second line contains n non-negative space-separated integers a₁, a₂, ..., a_n — the elements of the array that Petya's mother presented him. All integers in the input do not exceed 10⁹.

Output

If there is a pair of positions that make the array unsorted if swapped, then print the numbers of these positions separated by a space. If there are several pairs of positions, print any of them. If such pair does not exist, print -1. The positions in the array are numbered with integers from 1 to n.

Sample test(s)

input

1
1

output

-1

input

2
1 2

output

-1

input

4
1 2 3 4

output

1 2

input

3
1 1 1

output

-1

Note

In the first two samples the required pairs obviously don't exist.

In the third sample you can swap the first two elements. After that the array will look like this: 2 1 3 4. This array is unsorted.

Thuật toán:

• Ta nhận xét các trường hợp không có cách đổi:
• Chỉ có một phần tử.
• Có không quá hai phần tử.
• Có ba phần tử và phần tử cuối bằng phần tử đầu. ví dụ 4 6 4.
• Còn lại luôn có cách đổi. Do đó thử chọn hai phần tử bất kì khác nhau, thử đổi rồi kiểm tra xem có thỏa mãn đã sorted chưa? Nếu chưa thì đó là kết quả, thoát.

Code:

/* 
    Coder : Nguyen Duc Tam 
    template for contest
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<cctype>

using namespace std;

/*
    define for statement loop
*/
#define REP(i, start, end, step) for(int i = start; i < end; i += step)
#define DOWN(i, start, end, step) for(int i = start; i > end; i -= step)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

/*
    define operator bit
*/
#define L(x,i) ((x) << (i))
#define R(x,i) ((x) >> (i))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define NOT(a) (~(a))
#define SB(x,i) (OR((x), L(1, (i))))    // x | 1 << i 
#define CB(x,i) (AND((x),NOT(L(1,(i))))) // x & ~(1 << i)
#define TB(x,i) (AND((x), L(1,(i))))    // x & (1 << i) 

/*
    define init data    
*/
#define FILL(a,val) memset(a,val,sizeof(a));
#define INIT(a,l,r,val) REP(i,l,r,1) (a)[i] = val;

/*
    define convert data
*/
#define DIG(c) (int)((c) - '0')
#define CHR(c) (char)((c) + '0')
#define LOW(c) (char)((c) + 32)
#define UPP(c) (char)((c) - 32)

/*
    define math function    
*/
#define sqr(a) (a) * (a)
#define abs(a) (a < 0 ? -(a) : (a))

/*
    define find element in container very fast.
*/
#define LO(c,x) lower_bound(ALL(c),x)   
#define UP(c,x) upper_bound(ALL(c),x)
#define IOF(c,x) distance((c).begin(), LO((c),x))
#define IOL(c,x) distance((c).begin(), UP((c),x))
#define IN(c,x) binary_search(ALL(c),x)
#define ER(c,x) equal_range(ALL(c),x)

/*
    define geo
*/
#define DIS(p,q) sqrt(sqr(p.x - q.x) + sqr(p.y - q.y)) // khoang cach Euclide
#define DIM(p,q) abs(p.x - q.x) + abs(p.y - q.y) // khoang cach mahatan


/*
    define constant
*/
#define X first
#define Y second

struct Point
{
    double x, y;
    Point(){}
    Point(double x,double y):x(x), y(y){}   
};

struct Node
{
    int value;
    Node* next;
    Node(){}
    Node(int value, Node* next):value(value),next(next){}
};

struct Edge
{
    int src, dst, weight;
    Edge(){}
    Edge(int src, int dst, int weight):src(src), dst(dst), weight(weight){} 
    
};

struct Compare
{
    
    bool operator() (const int i, const int j)
    {
        return i > j;   
    }

    /*
    bool operator() (const Point& p, const Point& q)
    {
        return (p.x != q.x ? p.x < q.x : p.y < q.y);
    }   
    */
    /*
    bool operator()(const Edge& e, const Edge& f)
    {
        return  (e.weight != f.weight ? e.weight > f.weight : e.src != f.src ? 
            e.src < f.src : e.dst < f.dst); // inverse weight
    }
    */
};

    
const int DAY[13] = {-1,31,29,31,30,31,30,31,31,30,31,30,31};

const int dx4[4] = {-1, 0, 1, 0}; //U - R - D - L
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; //U - UR - R - DR - D - DL - L - UL 
const int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

typedef pair<int,int> II;
typedef pair<II,int> III;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned char UC; 

#define EPS 1e-7
#define OO (1LL<<31)-1
#define N 100005

vector<int>::iterator it, low, up; // using lower_bound, upper_bound
pair<vector<int>::iterator, vector<int>::iterator > bound;  // using function equal_range(first, last, x)
Compare comp;
Point p[2];
int n,a[N];
set<int> s;

bool isSorted()
{
    bool isSort;
    int i;
    //chck sort dec
    a[n] = -1;
    for(i=0;i<n-1;i++)
        if(a[i] < a[i+1]) break;
    isSort = (i == n-1 ? true : false);
    //check sort inc
    a[n] = OO;
    for(i = 0;i < n-1; i++)
        if(a[i] > a[i+1])break;
    isSort = isSort | (i == n - 1 ? true : false);
    return isSort;
}
void swap(int& x, int& y)
{
    int temp = x; x=y; y = temp;    
}

int main()
{
    #define Off  false
    if(Off)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }
    cin >> n;
    REP(i,0,n,1)
    {
        scanf("%d",&a[i]);
        s.insert(a[i]);
    }
    if(n < 3 || (int)s.size() == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    if(n==3 && a[0] == a[2])
    {
        cout << -1 << endl;
        return 0;
    }
    REP(i,1,n,1)
    {
        if(a[i] != a[i-1])
        {
            swap(a[i],a[i-1]);
            if(!isSorted())
            {
                cout << i << " " << i + 1 << endl;  
                break;
            }
            swap(a[i],a[i-1]);
        }
    }
    return 0;
}