One day, Twilight Sparkle is interested in how to sort a sequence of integers a1, a2, ..., an 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:

a1, a2, ..., an → an, a1, a2, ..., an - 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 ≤ 105). The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105).

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
//package little.pony.and.sort.by.shift;
import java.util.*;
public class LittlePonyAndSortByShift {
static class Node{
    int num;
    Node next;
    Node prev;
    
    public Node (int data){
        num =  data;
    }
}
static class Link {
    int count = 0;
    Node first;
    Node last;
    
    public Link(){
        first = null;
        last = first;
    }
    
    public void insert(int x){
        Node New = new Node(x);
        New.prev = last;
        last = New;
        if (first == null) {
            first = New;
            first.prev = null;
        }
    }
    public boolean check(){
        Node current = last;
        while(current.prev != null){
            if(current.num < current.prev.num) return false;
            current = current.prev;
        }
        return true;
    }
    public int shift(int c){
        int eq = 0;
        while(last.num <= first.num && count != c){
            Node temp = last;
            last = last.prev;
            temp.prev = null;
            first.prev = temp;
            first = temp;
            if(last.num == first.num) eq++;
            count++;
        }
        if (check()) {
            if(eq == c) return 0;
            return count;
        }
        return -1;
    }
}
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int x = s.nextInt();
        int d;
        Link a = new Link();
        for(int i = 0 ; i < x ; i++){
            d = s.nextInt();
            a.insert(d);
        }
        System.out.println(a.shift(x));
    }
    
}
