One day, Twilight Sparkle is interested in how to sort a sequence of integers a_1, a_2, ..., a_{n} in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning:a_1, a_2, ..., a_{n} → a_{n}, a_1, a_2, ..., a_{n} - 1. 

Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 10^5). The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

If it's impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.


-----Examples-----
Input
2
2 1

Output
1

Input
3
1 3 2

Output
-1

Input
2
1 2

Output
0

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
d = []
for i in range(1, n):
    d.append(a[i] - a[i - 1])
d.append(a[0] - a[n - 1])
cnt = 0
for i in range(0, n):
    if d[i] < 0:
        cnt += 1
        pos = i
if cnt == 0:
    print(0)
elif cnt > 1:
    print(-1)
else:
    print(n - pos - 1)


import sys
n = int(input())
l = [int(i) for i in input().split()]
l += [l[0]]
jump = False
j = -1
m = l[0]
for i in range(n):
    if l[i] > l[i+1]:
        if jump:
            print(-1)
            return
        jump = True
        j = i
    else:
        if jump:
            if l[i] > m:
                print(-1)
                return
            
if j == -1:
    print(0)
else:
    print(n-j-1)


n = int(input())
a = list(map(int,input().split(' ')))
p = 0
for i in range(n-1):
	if(a[i]>a[i+1]):
		p = i+1
b = a[p:]+a[:p]
for i in range(n-1):
	if(b[i]>b[i+1]):
		print(-1)
		break
else:
	print((n-p)%n)

#input
n=int(input())
alist=[int(x) for x in input().split()]

#variables
fault=0

#start of program
for i in range(n):
	if alist[i-1]<=alist[i]:
		pass

	else:
		fault+=1
		if fault>1:
			print(-1)
			quit()
		f=i

if fault==0:
	print(0)
	quit()

print((n-f)%n)

N = int(input())
place = N
word = True
numbers = list(map(int, input().split()))
for i in range(1, N):
    if numbers[i] < numbers[i - 1]:
        place = i
        for i in range(place + 1, place + N):
            if numbers[i % N] < numbers[i % N - 1]:
                word = False
                break
        break
if word == False:
    print(-1)
else:
    print(N - place)

def s(a, i):
   s = i
   while i+1 < len(a):
      if a[i] <= a[i+1]:
         i += 1
      else:
        return a[s:i+1]
   return a[s:i+1]

n = int(input())
a = list(map(int,input().split()))
b = s(a,0)
c = s(a,len(b))
if len(b) == n:
   print(0)
elif len(b) + len(c) == n and c[len(c)-1] <= b[0]:
    print(len(c))
else:
   print(-1)


n = int(input())
a = input().split(' ')
pre = int(a[0])
pos = n
for i in range(1,n):
    x = int(a[i])
    if x<pre:
        pre = x
        pos = i
        break
    pre = x
if pos==n:
    print(0)
else:
    ans = 0
    for j in range(pos,n):
        x = int(a[j])
        if x<pre:
            ans = -1
            break
        pre = x
    if ans==-1:
        print(-1)
    elif int(a[n-1])>int(a[0]):
        print(-1)
    else:
        print (n-pos)

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if is_sorted(a):
        return 0
    for i in range(1, len(a)):
        if a[i - 1] > a[i]:
            if is_sorted(a[i:] + a[:i]):
                return n - i
            else:
                return -1

print(solve())

n = int(input())
a = list(map(int, input().split()))
k = -1
for i in range(n - 1):
  if a[i] > a[i + 1]:
    k = i + 1
    break
else:
  print(0)
  return
for i in range(k, n - 1):
  if a[i] > a[0] or a[i] > a[i + 1]:
    print(-1)
    return
if a[k] > a[0] or a[-1] > a[0]:
  print(-1)
else:
  print(n - k)

n = int(input())
a = list(map(int,input().split()))

sub = []
for i in range(1,n):
    x = a[i] - a[i-1]
    sub.append(x)
sub.append(a[0]-a[-1])

c =  0
for i in range(n):
    if sub[i] < 0:
        c += 1
        pos = i
#print(sub)
if c == 0 :
    print(0)
elif c > 1:
    print(-1)
else:
    print(n - pos - 1)
        


n=int(input())
a=list(map(int,input().split()))
k=0
for i in range(n-1):
    if a[i]>a[i+1]:
        k+=1
if k==0:
    print(0)
elif k>1 or a[n-1]>a[0]:
    print(-1)
else:
    for i in range(n):
        if a[i]>a[i+1]:
            print(n-i-1)
            break

n = int(input())
a = []
ID = input().split()

for i in range(n):
    a.append(int(ID[i]))

k = 0
while (k < n - 1 and a[k] <= a[k + 1]):
    k += 1
    
i = k + 1
flag = False
while (i < n - 1):
    if (a[i] > a[i + 1]):
        flag = True
    i += 1

if (k < n - 1 and a[n - 1] > a[0]):
    flag = True
    
if flag == True:
    print(-1)
else:
    print(n - 1 - k)
    


n=int(input())
lst=list(map(int, input().split(' ')))
diffs=[]
for t in range(len(lst)-1):
    diffs.append(lst[t+1]-lst[t])
diffs.append(lst[0]-lst[-1])
lista=[x for x in diffs if x<0]

if len(lista)!=1:
    if max(diffs)==0:
        print(0)
    else:
        print(-1)
else:
    diffs.reverse()
    index=diffs.index(lista[0])
    if index==0:
        print(0)
    else:
        print(index)


n = int(input())
a = list(map(int,input().split()))
b = -1
for i in range(1,n):
	if a[i-1]>a[i]:
		b = i
		break
if b==-1:
	print(0)
else:
	c = a[b:]+a[:b]
	flag = 0
	for i in range(1,n):
		if c[i]<c[i-1]:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		print(n-b)





def main():
    n = int(input())
    a = list(map(int, input().split()))
    im = 1;
    while im < n and a[im] >= a[im - 1]:
        im += 1

    if sorted(a[im:] + a[:im]) == (a[im:] + a[:im]):
        print(n - im)
    else:
        print(-1)


def __starting_point():
    main()


__starting_point()

import sys

def minindex(alist):
    index = -1
    min = 1000000
    for idx, num in enumerate(alist):
        if num < min:
            index = idx
            min = num
    return index
            
def isSorted(array):
    min = 0
    for num in array:
        if num < min:
            return False
        min = num
    return True 


nums = int(sys.stdin.readline())

numbers = [int(num) for num in sys.stdin.readline().split()[0:nums]]

index = minindex(numbers)
min = numbers[index]


moves = 0
if index == 0:
    for num in range(nums-1, -1, -1):
        if num == 0:
            moves = 0
            break
        if numbers[num] == min:
            moves = moves + 1
        else:
            break

    newnumbers = numbers[index:nums-moves]
    if isSorted(newnumbers):
        print(moves)
    else:
        print(-1)

else:
    newnumbers = numbers[index:]
    newnumbers.extend(numbers[0:index])
    if isSorted(newnumbers):
        print(nums - index)
    else:
        print(-1)

n = int(input())
a = list(map(int,input().split()))
b = list()
c = list()
if a == list(sorted(a)):
    print(0)
    return
for i in range(1 , n):
    if a[i] < a[i-1]:
        b.append(i)
ans = True
if len(b) == 1:
    for i in range(b[0] , n):
        c.append(a[i])
    for i in range(b[0]):
        c.append(a[i])
    if c != list(sorted(a)):
        ans = False
if len(b) == 1 and ans:
    print(n - b[0])
else:
    print(-1)   

n = int(input())
a = list(map(int, input().split()))
p = 0
for i in range(n - 1):
    if (a[i] > a[i + 1]):
        p = i + 1
b = a[p:] + a[:p]
for i in range(n - 1):
    if (b[i] > b[i + 1]):
        print(-1)
        break
else:
    print((n - p) % n)

n = int(input())
a = list(map(int,input().split(' ')))
p = 0
for i in range(n-1):
	if(a[i]>a[i+1]):
		p = i+1
b = a[p:]+a[:p]
for i in range(n-1):
	if(b[i]>b[i+1]):
		print(-1)
		break
else:
	print((n-p)%n)

def naek(a,indeks):
    for x in range(indeks,len(a)-1):
        if a[x]>a[x+1]:
            return False
            pass
        pass
        pass
    return True
    pass

a=int(input())
a=list(map(int,input().split(" ")))
sor=True
for x in range(len(a)-1):
    if a[x]>a[x+1]:
        sor=False
        idx=x+1
        break
        pass
    pass

if sor:
    print (0)
else:
    if naek(a,idx):
        if a[len(a)-1] > a[0]:
            print (-1)
        else:
            print (len(a)-idx)
            pass
        pass
    else:
        print (-1)        
    pass

def naek(a,indeks):
    for x in range(indeks,len(a)-1):
        if a[x]>a[x+1]:
            return False
            pass
        pass
        pass
    return True
    pass

dum=0
a=int(input())
a=list(map(int,input().split(" ")))
sor=True
for x in range(len(a)-1):
    if a[x]>a[x+1]:
        sor=False
        idx=x+1
        break
        pass
    pass

if sor:
    print (0)
else:
    if naek(a,idx):
        if a[len(a)-1] > a[0]:
            print (-1)
        else:
            print (len(a)-idx)
            pass
        pass
    else:
        print (-1)        
    pass

n=int(input())
a=list(map(int,input().split()))
a.reverse()
aa=a+a
r=1
l=0
ans=-1
while r<2*n:
    while r<2*n:
        if aa[r-1]<aa[r]:
            break
        r+=1
    if r-l>=n:
        ans=l
        break
    l=r
    r+=1
print(ans)

n = list(map(int, input().split()))[0]
a = list(map(int, input().split()))

flag = 0
for i in range(1,n):
	if a[i] < a[i-1]:
		flag = i

ans = True
for i in range (flag+1,n-1):
	if a[i+1] < a[i] :
		ans = False

for i in range (flag-1) :
	if a[i+1] < a[i] :
		ans = False

if flag != 0 and a[n-1] > a[0] :
	ans = False

if not ans:
	print("-1")
else:
	print((n-flag)%n)

n = int(input())
t = list(map(int, input().split()))
i = 1
while i < n and t[i] >= t[i - 1]: i += 1
if i == n: print(0)
else:
    j = i + 1
    while j < n and t[j] >= t[j - 1]: j += 1
    print(-1 if j < n or t[0] < t[-1] else n - i)

import sys

n = int(sys.stdin.readline())

ok = True 
inc = True
last, res, i   = 0,0,0
first = 0

for num in sys.stdin.readline().split():
	num = int(num)
	if first == 0:
		first = num

	if last > num:
		if inc:
			inc = False
			res = n - i
		else :
			ok = False
	last = num	
	i = i + 1

if last > first:
	if inc:
		pass
	else:
		ok = False
	
if ok:
	print(res)
else:
	print(-1)