A sequence $a_1, a_2, \dots, a_k$ is called an arithmetic progression if for each $i$ from $1$ to $k$ elements satisfy the condition $a_i = a_1 + c \cdot (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 $b_1, b_2, \dots, b_n$. Find any index $j$ ($1 \le j \le n$), such that if you delete $b_j$ 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 \le n \le 2\cdot10^5$) — length of the sequence $b$. The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — elements of the sequence $b$.


-----Output-----

Print such index $j$ ($1 \le j \le 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.


-----Examples-----
Input
5
2 6 8 7 4

Output
4
Input
8
1 2 3 4 5 6 7 8

Output
1
Input
4
1 2 4 8

Output
-1


-----Note-----

Note to the first example. If you delete the $4$-th element, you can get the arithmetic progression $[2, 4, 6, 8]$.

Note to the second example. The original sequence is already arithmetic progression, so you can delete $1$-st or last element and you will get an arithmetical progression again.

Difficulty: interview

Starter code:

Solutions:
import sys 
from collections import defaultdict
input = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(x)

n = int(input())
arr = sorted([(j, i + 1) for i, j in enumerate(map(int, input().split()))])

if n <= 3:
  print(arr[0][1])
  return


a1, a2, a3 = arr[0][0], arr[1][0], arr[2][0]
c1, c2, c3 = a3 - a2, a3 - a1, a2 - a1

flag = True
x = a2
for i in range(n):
  if i == 0:
    continue 
  if arr[i][0] != x:
    flag = False 
    break
  else:
    x += c1

if flag:
  print(arr[0][1])
  return

flag = True
x = a1
for i in range(n):
  if i == 1:
    continue 
  if arr[i][0] != x:
    flag = False 
    break
  else:
    x += c2

if flag:
  print(arr[1][1])
  return


flag = []
x = a1
for i in range(n): 
  if arr[i][0] != x:
    flag.append(arr[i]) 
  else:
    x += c3

if len(flag) >= 2:
  print(-1)
else:
  print(flag[0][1])

n = int(input())
b = list(map(int, input().split()))
b_ = []
for i, t in enumerate(b):
    b_.append([t, i+1])
b_.sort()


def solve(s):
    def check(a):
        if len(a) <= 1:
            return True
        delta = a[1] - a[0]
        for i in range(1, len(a) - 1):
            if a[i + 1] - a[i] != delta:
                return False
        return True

    if check([x[0] for x in s[1:]]):
        # print('a')
        return s[0][1]
    if check([x[0] for x in s[:-1]]):
        # print('b')
        return s[-1][1]
    if check([x[0] for x in s[:1] + s[2:]]):
        # print('c') 
        return s[1][1]
    if check([x[0] for x in s[:-2] + s[-1:]]):
        # print('d')
        return s[-2][1]

    # mid
    t = []
    for i in range(len(s) - 1):
        t.append(s[i+1][0] - s[i][0])
    # print(t)

    i = 0
    while t[i] == t[0]:
        i += 1
    j = len(t) - 1
    while t[j] == t[-1]:
        j -= 1

    if t[0] == t[-1]:
        if i != j - 1:
            return -1
        if t[i] + t[j] != t[0]:
            return -1
        return s[j][1]
    else:
        if i != j:
            return -1
        if i == 1 and t[0] + t[1] == t[2]:
            return s[1][1]
        if j == len(t) - 2 and t[j] + t[j+1] == t[j - 1]:
            return s[len(t) - 1][1]
        return -1


print(solve(b_))


n = int(input())
a = []
i = 0
for el in map(int, input().split()):
    a.append((el, i))
    i += 1
a.sort()
if n == 2:
    print(1)
    return
st = a[2][0] - a[1][0]
for i in range(1, n - 1):
    if a[i + 1][0] - a[i][0] != st:
        break
else:
    print(a[0][1] + 1)
    return
st = a[2][0] - a[0][0]
for i in range(2, n - 1):
    if a[i + 1][0] - a[i][0] != st:
        break
else:
    print(a[1][1] + 1)
    return
st = a[1][0] - a[0][0]
i = 1
found = -1
while i < n - 1:
    if a[i + 1][0] - a[i][0] != st:
        if found != -1:
            print(-1)
            return
        else:
            found = i + 1
            i += 1
    i += 1
t = a.pop(found)
for i in range(n - 2):
    if a[i + 1][0] - a[i][0] != st:
        print(-1)
        break
else:
    print(t[1] + 1)
    return


import sys
from collections import Counter
from operator import itemgetter

n = int(sys.stdin.readline().strip())
if n < 3:
    print('1')
    return

times = list(enumerate(map(int, (sys.stdin.readline().split()))))
times.sort(key=itemgetter(1))

origindices = [t[0] for t in times]
times = [t[1] for t in times]


# check if we can remove the first
c = times[2] - times[1]
a = times[1]
success = True
for i in range(2,n):
    if times[i] != a + c * (i - 1):
        success = False
        break

if success:
    print(origindices[0] + 1)
    return


# check if we can remove the second
a = times[0]
c = times[2] - times[0]
success = True
for i in range(2, n):
    if times[i] != a + c * (i - 1):
        success = False
        break

if success:
    print(origindices[1] + 1)
    return


# check if we can remove any other
removednum = 1 # if everything is correct (and we don't have to delete any element), we can just delete the first one
success = True
a = times[0]
c = times[1] - times[0]
for i in range(2,n):
    if (removednum == 1 and times[i] != a + c * i) \
       or (removednum != 1 and times[i] != a + c * (i - 1)):
        # print(f'Found that {times[i]} is not equal to {a + c * i} {a}, {i}, {c}')
        if removednum == 1:
            removednum = i # maybe it will still work if we remove this one; add 1 to shift index
        else:
            # otherwise, we already have removed an element,
            # so we must conclude that there is no way to make this succeed
            success = False
            break

if success:
    print(origindices[removednum] + 1)
    return


# This should only happen when everything fails:
print(-1)