老爷爷与老奶奶

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

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

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

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

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

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

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

彩排的时候,我记得被放置了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。

情人节邀请赛之木姐姐的情人节梦录[Marathon]

未参加
状态
已结束
规则
OI
题目
20
开始于
2015-02-13 12:00
结束于
2015-02-15 12:00
持续时间
48.0 小时
主持人
参赛人数
273