A sequence a1,a2,…,ak is called an arithmetic progression if for each i from 1 to k elements satisfy the condition ai=a1+c⋅(i−1) for some fixed c

.

For example, these five sequences are arithmetic progressions: [5,7,9,11]

, [101], [101,100,99], [13,97] and [5,5,5,5,5]. And these four sequences aren't arithmetic progressions: [3,1,2], [1,2,4,8], [1,−1,1,−1] and [1,2,3,3,3]

.

You are given a sequence of integers b1,b2,…,bn

. Find any index j (1≤j≤n), such that if you delete bj from the sequence, you can reorder the remaining n−1

elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.

Input

The first line of the input contains one integer n

(2≤n≤2⋅105) — length of the sequence b. The second line contains n integers b1,b2,…,bn (−109≤bi≤109) — elements of the sequence b

.

Output

Print such index j

(1≤j≤n), so that if you delete the j-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.

题意：给你一组数，问你能不能去其中掉一个数，然后把剩下的数排序后形成等差数列

思路：分别判断第一个和第二个是不是要去掉的数，是就找出来了，不是就有了公差，然后根据公差判断要去掉哪个数，如果去掉一个数后发现还是不能形成等差数列，那么输出-1

代码：

#include <cstdio>
#include<math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#include<stdio.h>
#include<string.h>
#define MAX 150000
#include<set>
int n;
int a[500000],b[500000];
void js(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(b[i]==x)
        {
            printf("%d\n",i);
            return;
        }
    }
}
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(a+1,a+1+n);
    if(n<=3)
    {
        printf("1\n");
        return 0;
    }
    int flag=0,d=a[3]-a[2];
    for(int i=4;i<=n;i++)
    {
        if(a[i]-a[i-1]!=d)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)
    {
        js(a[1]);
        return 0;
    }
    flag=0;d=a[3]-a[1];
    for(int i=4;i<=n;i++)
    {
        if(a[i]-a[i-1]!=d)
        {
            flag=1;
            break;
        }
    }
    if(flag==0)
    {
        js(a[2]);
        return 0;
    }
    d=a[2]-a[1];flag=0;
    for(int i=3;i<=n;i++)
    {
        if(a[i]-a[i-1]!=d)
        {
            if(flag==0)
            {
                flag=a[i];
                if(a[i+1]-a[i-1]==d||i==n) i++;
                else
                {
                    printf("-1\n");
                    return 0;
                }
            }
            else
            {
                printf("-1\n");
                return 0;
            }
        }
    }
    if(flag==0)
    {
        js(a[n]);
    }
    else
    {
        js(flag);
    }
}