← 返回题目列表

Codeforces · 454/B

B. 小马驹和按 Shift 排序

中文机器翻译题面 查看原题

有一天,Twilight Sparkle 对如何以非降序对整数序列 a1, a2, ..., an 进行排序感兴趣。作为一只年轻的独角兽,她唯一能执行的操作就是单位转换。也就是说,她可以将序列的最后一个元素移动到其开头:

a1, a2, ..., an → an, a1, a2, ..., an - 1。

帮助暮光闪闪计算:对序列进行排序最少需要多少次操作?

输入

第一行包含一个整数 n (2 ≤ n ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105)。

输出

如果无法对序列进行排序则输出-1。否则输出 Twilight Sparkle 对其进行排序所需的最小操作数。

示例

输入 #1

2
2 1

输出 #1

1

输入 #2

3
1 3 2

输出 #2

-1

输入 #3

2
1 2

输出 #3

0