B - Little Pony and Sort by Shift

2024-04-07 04:32

文章标签 little sort shift pony

本文主要是介绍B - Little Pony and Sort by Shift，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Submit Status Practice CodeForces 454B

Description

One day, Twilight Sparkle is interested in how to sort a sequence of integers a₁, a₂, ..., 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₁, a₂, ..., a_n → a_n, a₁, a₂, ..., 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⁵). The second line contains n integer numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵).

Output

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

Sample Input

Input

2
2 1

Output

Input

3
1 3 2

Output

-1

Input

2
1 2

Output

这道题觉得非常水，但却一直wa，在训练赛的最后12提交过。。汗颜

思路：先将数组复制一遍放在接在数组后面，找到数组中最小的那个数在数组中出现的第一个位置，然后只要从他开始有连续的n个递增（前后相等也可），就可以。。。

第一次的代码：（思路比较智障）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{int x;while(cin>>x){int max=0,t,t1,max1=0;for(int i=0; i<x; i++){scanf("%d",&a[i]);if(a[i]>max){max=a[i];t=i;}if(a[i]>=max1){max1=a[i];t1=i;}}for(int i=t;i<x;i++){if(a[i]!=max)break;else{t=i;}}int flag1=0,flag2=0,flag3=0,flag4=0;for(int i=1;i<t1;i++){if(a[i-1]>a[i])flag1=1;}for(int i=t1+2;i<x;i++){if(a[i-1]>a[i])flag2=1;}for(int i=1;i<t;i++){if(a[i-1]>a[i])flag3=1;}for(int i=t+2;i<x;i++){if(a[i-1]>a[i])flag4=1;}if(flag1==0&&flag2==0&&(a[x-1]<=a[0]||t1==x-1))printf("%d\n",x-1-t1);else{if(flag3==0&&flag4==0&&(a[x-1]<=a[0]||t==0))printf("%d\n",x-1-t);elseprintf("-1\n");}}return 0;
}