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:  a_1 ≤ a_2 ≤ ... ≤ a_{n};  a_1 ≥ a_2 ≥ ... ≥ 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^5). The second line contains n non-negative space-separated integers a_1, a_2, ..., a_{n} — the elements of the array that Petya's mother presented him. All integers in the input do not exceed 10^9.


-----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.


-----Examples-----
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.

Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
n = int(input())
l = [int(i) for i in input().split()]
if n == 1 or n == 2:
	print(-1)
	exit()
if len(set(l)) == 1:
	print(-1)
	exit()

def rev(l):
	return all((l[i] >= l[i + 1] for i in range(n - 1)))

def srt(l):
	return all((l[i] <= l[i + 1] for i in range(n - 1)))
if rev(l) or srt(l):
	for i in range(1, n):
		if l[i] != l[i - 1]:
			print(i, i + 1)
			exit()
f = 0
cnt = 0
for i in range(1, n):
	if l[i] != l[i - 1]:
		if cnt == 3:
			break
		(l[i], l[i - 1]) = (l[i - 1], l[i])
		if srt(l) or rev(l):
			cnt += 1
			(l[i], l[i - 1]) = (l[i - 1], l[i])
		else:
			print(i, i + 1)
			exit()
else:
	print(-1)


def solve(arr):
	if len(arr) <= 2 or len(set(arr)) == 1:
		return [-1]
	else:
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] != arr[j]:
					(arr[i], arr[j]) = (arr[j], arr[i])
					if arr != sorted(arr) and arr != list(reversed(sorted(arr))):
						return [i + 1, j + 1]
					else:
						(arr[i], arr[j]) = (arr[j], arr[i])
	return [-1]

def __starting_point():
	n = int(input())
	arr = list(map(int, input().split()))
	print(*solve(arr))
__starting_point()


import sys
n = int(input())
a = [int(s) for s in input().split()]
for i in range(0, 2):
	for j in range(i + 1, n):
		if a[i] != a[j]:
			r = a[j]
			a[j] = a[i]
			a[i] = r
			lol = True
			lol1 = True
			for h in range(1, n):
				if a[h - 1] > a[h]:
					lol = False
				if a[h - 1] < a[h]:
					lol1 = False
			if not lol and (not lol1):
				print(i + 1, j + 1)
				sys.exit()
			else:
				r = a[j]
				a[j] = a[i]
				a[i] = r
print(-1)


import sys

def solve():
	(n,) = rv()
	(a,) = rl(1)
	for i in range(min(10, n - 1)):
		for j in range(max(i + 1, n - 10), n):
			if a[i] != a[j]:
				(a[i], a[j]) = (a[j], a[i])
				if notsorted(a):
					print(i + 1, j + 1)
					return
				(a[i], a[j]) = (a[j], a[i])
	count = 0
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
			if notsorted(a):
				print(i + 1, i + 2)
				return
			(a[i], a[i + 1]) = (a[i + 1], a[i])
			count += 1
		if count == 100:
			break
	print(-1)

def notsorted(a):
	(first, second) = (True, True)
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			first = False
			break
	for i in range(len(a) - 1):
		if a[i] < a[i + 1]:
			second = False
			break
	return True if not first and (not second) else False

def prt(l):
	return print(''.join(l))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


def hehe(a, n):
	if n == 1 or n == 2:
		return -1
	a1 = list(a)
	for i in range(1, n - 1, 1):
		if a1[i - 1] == a1[i] == a1[i + 1]:
			continue
		elif a1[i - 1] <= a1[i] <= a1[i + 1] or a1[i - 1] >= a1[i] >= a1[i + 1]:
			if a1[i - 1] == a1[i]:
				return [i + 1, i + 2]
			elif a1[i] == a1[i + 1]:
				return [i, i + 1]
			else:
				return [i, i + 1]
		elif a1[i - 1] < a1[i] > a1[i + 1] or a1[i - 1] > a1[i] < a1[i + 1]:
			if a1[i - 1] != a1[i + 1]:
				return [i, i + 2]
			elif i < n - 2:
				if a1[i + 2] == a1[i]:
					return [i, i + 1]
	return -1
n = int(input())
a = input().split()
a = [int(i) for i in a]
answer = hehe(a, n)
if answer == -1:
	print(-1)
else:
	print(*answer, sep=' ')


n = int(input())
arr = list(map(int, input().split()))
(a, b) = (-1, -1)
for i in range(1, n):
	if arr[i - 1] == arr[i]:
		continue
	(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
	(up, down) = (True, True)
	for j in range(1, n):
		if arr[j - 1] < arr[j]:
			down = False
		if arr[j - 1] > arr[j]:
			up = False
	if not up and (not down):
		(a, b) = (i - 1, i)
		break
	(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
print(-1 if a == -1 else str(a + 1) + ' ' + str(b + 1))


import sys
import random
n = int(input())
a = [int(x) for x in input().split()]

def flat():
	for i in range(1, n):
		if a[i] != a[0]:
			return False
	return True
if n < 3 or flat():
	print(-1)
	sys.exit()

def sorted_asc():
	for i in range(1, n):
		if a[i] > a[i - 1]:
			return False
	return True

def sorted_desc():
	for i in range(1, n):
		if a[i] < a[i - 1]:
			return False
	return True
for i in range(0, 100000):
	be = random.randrange(0, n)
	en = be
	while en == be:
		en = random.randrange(0, n)
	if a[be] == a[en]:
		continue
	(a[be], a[en]) = (a[en], a[be])
	if not sorted_asc() and (not sorted_desc()):
		print(be + 1, en + 1)
		sys.exit()
	(a[be], a[en]) = (a[en], a[be])
print(-1)


n = int(input())
jim = []
p = list(map(int, input().split()))
if n == 1 or n == 2 or len(set(p)) == 1:
	print(-1)
elif n == 3 and len(set(p)) == 2:
	ka = [x for x in p]
	if p[0] == p[-1]:
		print(-1)
	elif p[0] == p[1]:
		print(2, 3)
	else:
		print(1, 2)
elif len(set(p)) >= 3:
	kam = list(set(p))
	jim.append(kam[0])
	jim.append(kam[1])
	jim.append(kam[2])
	jim.sort()
	da = p.index(jim[0]) + 1
	dra = p.index(jim[1]) + 1
	dla = p.index(jim[2]) + 1
	if dra < da and dra < dla:
		print(da, dla)
	else:
		print(dra, min(da, dla))
else:
	ka = [x for x in p]
	ka.sort(reverse=True)
	ja = sorted(p)
	lam = 1
	for y in range(n):
		if p[y] != p[lam]:
			(p[y], p[lam]) = (p[lam], p[y])
			if p != ja and p != ka:
				print(y + 1, lam + 1)
				break
			else:
				(p[y], p[lam]) = (p[lam], p[y])
		else:
			pass


n = int(input())
data = list(map(int, input().split()))
mins = [0 for i in range(n)]
maxs = [0 for i in range(n)]
mins_back = [0 for i in range(n)]
maxs_back = [0 for i in range(n)]
min_ = data[0]
mins[0] = 0
max_ = data[0]
maxs[0] = 0
if n == 2:
	print(-1)
	exit(0)
for i in range(n):
	if data[i] < min_:
		min_ = data[i]
		mins[i] = i
	elif i > 0:
		mins[i] = mins[i - 1]
	if data[i] > max_:
		max_ = data[i]
		maxs[i] = i
	elif i > 0:
		maxs[i] = maxs[i - 1]
for i in range(1, n - 1):
	if data[i] != data[mins[i]]:
		if mins[i] == i - 1 and data[mins[i]] < data[i + 1]:
			print(i + 1, mins[i] + 1)
			exit(0)
		if data[i - 1] > data[mins[i]] and data[mins[i]] < data[i + 1]:
			print(i + 1, mins[i] + 1)
			exit(0)
	if data[i] != data[maxs[i]]:
		if maxs[i] == i - 1 and data[maxs[i]] > data[i + 1]:
			print(i + 1, maxs[i] + 1)
			exit(0)
		if data[i - 1] < data[maxs[i]] and data[maxs[i]] > data[i + 1]:
			print(i + 1, maxs[i] + 1)
			exit(0)
data = data[::-1]
min_ = data[0]
mins[0] = 0
max_ = data[0]
maxs[0] = 0
for i in range(n):
	if data[i] < min_:
		min_ = data[i]
		mins[i] = i
	elif i > 0:
		mins[i] = mins[i - 1]
	if data[i] > max_:
		max_ = data[i]
		maxs[i] = i
	elif i > 0:
		maxs[i] = maxs[i - 1]
for i in range(1, n - 1):
	if data[i] != data[mins[i]]:
		if mins[i] == i - 1 and data[mins[i]] < data[i + 1]:
			print(n - i, n - mins[i])
			exit(0)
		if data[i - 1] > data[mins[i]] and data[mins[i]] < data[i + 1]:
			print(n - i, n - mins[i])
			exit(0)
	if data[i] != data[maxs[i]]:
		if maxs[i] == i - 1 and data[maxs[i]] > data[i + 1]:
			print(n - i, n - maxs[i])
			exit(0)
		if data[i - 1] < data[maxs[i]] and data[maxs[i]] > data[i + 1]:
			print(n - i, n - maxs[i])
			exit(0)
(data[0], data[-1]) = (data[-1], data[0])
if data[0] == data[-1]:
	print(-1)
	exit(0)
for i in range(1, n - 1):
	if data[i] < data[i - 1] and data[i] < data[i + 1]:
		print(1, n)
		exit(0)
	if data[i] > data[i - 1] and data[i] > data[i + 1]:
		print(1, n)
		exit(0)
print(-1)


n = int(input())
t = list(map(int, input().split()))
if n < 3 or (n == 3 and t[0] == t[2]) or all((i == t[0] for i in t)):
	print(-1)
else:
	i = 1
	while t[i] == t[i - 1]:
		i += 1
	if i > 1:
		print('2 ' + str(i + 1))
	elif t[0] < t[1]:
		if t[1] <= t[2]:
			print('1 2')
		elif t[0] == t[2]:
			if t[0] == t[3]:
				print('2 3')
			else:
				print('3 4')
		else:
			print('1 3')
	elif t[1] >= t[2]:
		print('1 2')
	elif t[0] == t[2]:
		if t[0] == t[3]:
			print('2 3')
		else:
			print('3 4')
	else:
		print('1 3')


import random
import sys
n = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
X = sorted(L)
XX = sorted(L, reverse=True)
K = {}
for i in range(n):
	item = L[i]
	if item in K:
		K[item].append(i)
	else:
		K[item] = [i]
if len(X) <= 2 or X[0] == X[-1] or (len(X) == 3 and (L == [X[0], X[-1], X[0]] or L == [X[-1], X[0], X[-1]])):
	print(-1)
else:
	x = X[0]
	y = X[-1]
	a = random.randint(0, len(K[x]) - 1)
	b = random.randint(0, len(K[y]) - 1)
	a = K[x][a]
	b = K[y][b]
	(L[a], L[b]) = (L[b], L[a])
	while L == X or L == XX:
		(L[a], L[b]) = (L[b], L[a])
		a = random.randint(0, len(K[x]) - 1)
		b = random.randint(0, len(K[y]) - 1)
		a = K[x][a]
		b = K[y][b]
		(L[a], L[b]) = (L[b], L[a])
	print(a + 1, b + 1)


n = int(input())
a = [int(i) for i in input().split()]
b = len(set(a))
c = sorted(a, reverse=True)
if n == 1 or n == 2 or b == 1:
	print('-1')
elif n == 3:
	if b == 2:
		if a[0] == a[2]:
			print('-1')
		elif a[0] == a[1]:
			print('2 3')
		else:
			print('1 2')
	elif a[1] != max(a[0], a[1], a[2]):
		print(a.index(c[0]) + 1, '2')
	else:
		print(a.index(c[2]) + 1, '2')
elif n == 4:
	if b == 2:
		if a[0] == a[3]:
			if a[0] == a[1] or a[0] == a[2]:
				print('2 3')
			else:
				print('1 2')
		elif a[0] == a[1]:
			if a[0] == a[2]:
				print('4 3')
			else:
				print('2 3')
		elif a[0] == a[2]:
			print('1 2')
		elif a[1] == a[2]:
			print('1 2')
		elif a[1] == a[3]:
			print('1 2')
		else:
			print('2 3')
	elif b == 3:
		if c[0] == c[1]:
			if a.index(c[3]) != 2:
				print(a.index(c[3]) + 1, '3')
			elif a.index(c[3]) != 1:
				print(a.index(c[3]) + 1, '2')
		elif a.index(c[0]) != 2:
			print(a.index(c[0]) + 1, '3')
		elif a.index(c[0]) != 1:
			print(a.index(c[0]) + 1, '2')
	elif b == 4:
		if a.index(c[0]) != 2:
			print(a.index(c[0]) + 1, '3')
		elif a.index(c[0]) != 1:
			print(a.index(c[0]) + 1, '2')
elif n > 4:
	i = 0
	while a[i] == a[0]:
		i += 1
	if i > 3:
		print(i + 1, '2')
	else:
		d = list(a)
		for i in range(n - 4):
			a.pop()
		c = sorted(a, reverse=True)
		b = len(set(c))
		if b == 2:
			if a[0] == a[3]:
				if a[0] == a[1] or a[0] == a[2]:
					print('2 3')
				else:
					print('1 2')
			elif a[0] == a[1]:
				if a[0] == a[2]:
					print('4 3')
				else:
					print('2 3')
			elif a[0] == a[2]:
				print('1 2')
			elif a[1] == a[2]:
				print('1 2')
			elif a[1] == a[3]:
				print('1 2')
			else:
				print('2 3')
		elif b == 3:
			if c[0] == c[1]:
				if a.index(c[3]) != 2:
					print(a.index(c[3]) + 1, '3')
				elif a.index(c[3]) != 1:
					print(a.index(c[3]) + 1, '2')
			elif a.index(c[0]) != 2:
				print(a.index(c[0]) + 1, '3')
			elif a.index(c[0]) != 1:
				print(a.index(c[0]) + 1, '2')
		elif b == 4:
			if a.index(c[0]) != 2:
				print(a.index(c[0]) + 1, '3')
			elif a.index(c[0]) != 1:
				print(a.index(c[0]) + 1, '2')


def list_comp(x, y):
	for i in range(0, len(x)):
		if x[i] != y[i]:
			return False
	return True

def main():
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n <= 2:
		print(-1)
		exit()
	b = a.copy()
	b.sort()
	c = a.copy()
	c.sort(reverse=True)
	for i in range(1, n):
		if a[i] != a[i - 1]:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
			if list_comp(a, b) or list_comp(a, c):
				(a[i], a[i - 1]) = (a[i - 1], a[i])
			else:
				print(i, i + 1)
				exit()
	print(-1)
main()


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log
import math
from itertools import permutations
from copy import deepcopy
from sys import setrecursionlimit

def main():
	n = int(input())
	a = list(map(int, input().split()))
	z = len(set(a))
	if z == 1 or n == 2:
		print(-1)
	elif z == 2 and (a[0] == a[-1] and n == 3):
		print(-1)
	else:
		ind = 0
		for i in range(n - 1):
			if a[i] != a[i + 1]:
				ind = i
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				break
		(x, y, w) = (0, 0, 0)
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				x += 1
			elif a[i] < a[i + 1]:
				y += 1
			else:
				w += 1
		if y + w == n - 1:
			if ind == n - 2:
				print(-1)
			else:
				(a[ind + 1], a[ind]) = (a[ind], a[ind + 1])
				for i in range(ind + 1, n - 1):
					if a[i] != a[i + 1]:
						print(i + 1, i + 2)
						break
		elif x + w == n - 1:
			if ind == n - 2:
				print(-1)
			else:
				(a[ind + 1], a[ind]) = (a[ind], a[ind + 1])
				for i in range(ind + 1, n - 1):
					if a[i] != a[i + 1]:
						print(i + 1, i + 2)
						break
		else:
			print(ind + 1, ind + 2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
lis = list(map(int, input().split()))
sor = sorted(lis)
res = sor[::-1]
for i in range(1, n):
	if lis[i - 1] == lis[i]:
		continue
	for j in range(i - 1, n):
		if lis[i] != lis[j]:
			(lis[i], lis[j]) = (lis[j], lis[i])
			if lis != sor and lis != res:
				print(i + 1, j + 1)
				exit()
			(lis[i], lis[j]) = (lis[j], lis[i])
	i += 1
print(-1)