描述

一日，和木姑娘在校园里散步，木姑娘突然搀住我的手，说到：“老头子，你看这地上的垃圾”。

呵呵，这是我们小学的时候排练的舞台剧里的台词。她的记忆力真好。

那个时候我和她分别扮演老爷爷和老奶奶。老奶奶馋着老爷爷一步一步走着，老奶奶看到地上的垃圾到处乱放，说到：

“老头子，你看这地上的垃圾。唉，现在的年轻人真是的。”

老爷爷咳嗽一声，说到：“是呀！来来来，就让我们俩来把这些垃圾整理好吧。”

那个时候的事情，恍如隔日，真的是很美好。

彩排的时候，我记得被放置了n件大小不同的垃圾排成一排，体积依次为a[1],a[2],...,a[n]。

每次老爷爷和老奶奶会将最后一件垃圾移动到最前面，体积变成a[n],a[1],a[2],...,a[n-1]。

经过最少需要的操作，使得序列成为不下降数列，就算完成了任务。

格式

输入格式

第一行有一个整数n，满足2<=n<=100000。

第二行有n个整数，分别为a[1],a[2],...,a[n]，满足对于每一个数字a[i]，有1<=a[i]<=100000。

输出格式

如果可以通过这样的操作实现不下降数列，则输出最少操作次数。否则输出-1。

样例1

样例输入1

2
2 1

样例输出1

1

样例2

样例输入2

3
1 3 2

样例输出2

-1

样例3

样例输入3

2
1 2

样例输出3

0

限制

60%的数据，n<=20。
100％的数据，n<=100000。