program exercise(input,output);
var n,x,y,i:longint;
a:array[0..100001]of longint;
begin
readln(n);
x:=200001;
y:=0;
for i:=0 to n-1 do
begin
read(a[i]);
if (x>a[i])or((a[i]=x)and(a[(n+i-1) mod n]>a[i])) then
begin
x:=a[i];
y:=i;
end;
end;
readln;
for i:=y to y+n-2 do
if a[i mod n]>a[(i+1) mod n] then
begin
writeln(-1);
exit;
end;
writeln((n-y) mod n);
end.

首先在原数列后面接一个一样的新数列
然后从原数列起点一直顺序读到新数列终点（循环）

出现长度为n的不降序列时，当前循环i值即为终点，则移走了2*n-i堆垃圾。如果读到最后都不出现长度为n的不降序列，输出-1

需要注意的是一个特例：若出现长度为n的不降序列时i=n，则原序列就是不降序列，所以输出0（不用再去读新数列）

下面是个我自己画给自己，帮助理解的模型，假设n=5， a3,a4,a5,a1,a2是一个不降序列。

a1 a2 //a3 a4 a5 a1 a2 //a3 a4 a5

读到a2时发现a3,a4,a5,a1,a2是一个不降序列（这时i=7)，那么此时被移到前面的垃圾是a3,a4,a5，共2*n-i=2*5-7=3(堆)

#include<stdio.h>
int main( )
{
int n,a[200010],sum=1,i;
scanf("%d",&n);

for(i=1;i<=n;i++)
scanf("%d",&a[i]);

for(i=n+1;i<=2*n-1;i++)
a[i]=a[i-n];

for(i=2;i<=2*n-1;i++)
{
if(a[i]>=a[i-1]) sum++;
else sum=1;
if(sum==n) { if(i==n) printf("0"); else printf("%d",2*n-i);break;}
}

if(sum!=n) printf("-1");

return 0;
}

#include<cstdio>
#include<iostream>
using namespace std;
int main() {
int n,x,y,y1,ans=0;
scanf("%d",&n);
scanf("%d",&y);
y1=y;
for(int i=2;i<=n;++i){
scanf("%d",&x);
if (x<y) {
if (ans!=0) ans=-1;
else ans=n-i+1;
}
if (ans==-1) break;
y=x;
}
if (y1<y&&ans!=0) ans=-1;
printf("%d",ans);
return 0;
}

n^2暴力加剪枝，轻松ac
#include<cstdio>
using namespace std;
int a[100010];
int main()
{
int i,j,n;
scanf("%d",&n);
for (i=1; i<=n; ++i) scanf("%d",&a[i]);
a[n+1]=a[1];
int t,ans,k;
i=n+1;
//for (i=n+1; i>=2; --i)
while (i>=2)
{
t=i;
k=a[i];
ans=1;
while (ans<n)
{
++t;
if (t>n+1) t=2;
if (a[t]<k) { if (t>i) {printf("-1"); return 0;} i=t+1; break;}
k=a[t];
++ans;

}
if (ans==n) { printf("%d",n+1-i); return 0;}
--i;
}
printf("-1");
return 0;
}

满足题意的序列 当且仅当序列最多有两段上升的子序列，且第二个子序列最后一个（最高位）<=第一个子序列的第一位（最低位）

可以把原数列视为一个环，从下标为pos的数开始遍历，如果是不下降数列，那么输出(n-pos+1) mod n,否则输出-1。
很显然，这个数必须是最小值才有可能是不下降数列。
问题是，有多个最小值的情况怎么办呢？
很显然，如果这几个最小值不能组成一个链，那么直接输出-1（因为不论从那个最小值开始遍历，途中一定会在已经遇到比最小值大的数的情况下遇到最小值）。
否则从最小值链的头部开始遍历（因为如果不从头部开始遍历，同样会在已经遇到比最小值大的数的情况下遇到最小值）。

Pascal Code

var
a:array[1..100000] of longint;
n,i,pos,l,num,min,j:longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
num:=0;
l:=0;
j:=0;
min:=maxlongint;
for i:=1 to n do
if a[i]<min then min:=a[i]; //寻找最小值
for i:=1 to n do
if a[i]=min then inc(num); //计算最小值个数
i:=0;
repeat
i:=i mod n+1; //计算下一个数的下标
inc(j);
if (a[i]=min) and (l=0) then pos:=i; //记录当前最小值链的头部
if a[i]=min then inc(l) //更新长度
else l:=0;
until (l=num) or (j>2*n);
if l<num //长度不到最小值数量
then begin
writeln(-1);
halt;
end;
i:=pos;
repeat
i:=i mod n+1;
if (a[i]<a[(i+n-2) mod n+1{计算上一个数下标}]) and (i<>pos) //不能构成不下降数列
then begin
writeln(-1);
halt;
end;
until i=pos;
writeln((n-pos+1) mod n);
end.

先将数列反过来，然后复制一份接到后边，
现在从最左边开始扫，
只要扫描到长度为n的不增序列即可输出起点的index，
扫描时若发现a[i]>a[i-1]则重新取i为起点，
如果直到最后都找不到长为n的不增序列则输出-1，
时间复杂度和空间复杂度均为O(n).

###Code
#include<cstdio>
int a[200005];
int main()
{
int n;
scanf("%d",&n);
for(int i=n-1;i>=0;i--)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
int res=0;
bool isok=0;
for(int i=1;i<2*n;i++)
{
if(a[i]>a[i-1])res=i;
if(i-res+1==n)
{
isok=1;
break;
}
}
if(isok)printf("%d",res);
else printf("-1");
return 0;
}

既然是把后面的元素逐一丢到前面去的操作,那把原序列复制一份接到后边,比如
a[0],a[1],...,a[n-1],a[n]=a[0],a[n+1]=a[1],...,a[2n-1]=a[n-1]
这样我们就只需要在这个序列里找到长度为n的连续子串a[i],a[i+1],...,a[i+n-1],使得它为不降序列.
操作次数则是n-i.
考虑怎么方便地判定一个序列是不是不降序列.
我们对原序列进行差分,这样如果序列是不降序列,它的差分必定没有任何数是负数(在这里我们用后面的元素减去前面的元素).
然后开两个指针L和R,并且R-L+1=n-1,代表了子串差分值的起始和结束,从右往左扫一遍,扫的时候维护负数的个数即可.

##Code
using namespace std;

int n;
int a[400000];
int d[400000];

int main()
{
n=getint();
for(int i=0;i<n;i++)
a[i+n]=a[i]=getint();

for(int i=0;i<2*n;i++)
d[i]=a[i+1]-a[i];

int r=2*n-2;
int l=n;
int cnt=0;
bool able=false;

for(int i=l+1;i<=r;i++)
if(d[i]<0) cnt++;

int res=0;
for(;l!=0;l--,r--,res++)
{
if(d[l]<0) cnt++;
if(cnt==0) { able=true; break; }
if(d[r]<0) cnt--;
}

if(n==1)
{ able=true; res=0; }

if(able) printf("%d\n",res);
else printf("-1\n");

return 0;
}

分析：
①设原数列为A，A的操作具有周期性，因为调了n次回到原型

②构造数列B，使得B的长度为n+n-1，对于1<=i<=n，B[i]=A[i]，对于n<i<2n，B[i]=A[i-n]，例如：

A数列为3 4 5 1 2

B数列为 3 4 5 1 2 3 4 5 1，

现在的目标就是在A,B间建立联系

③A数列操作后与B数列长度为n的连续子序列一一对应

④若B数列以i开头的长度为n的连续子序列为不下降子序列，则A数列最少进行(n-i+1)%n次操作后为不下降子序列

⑤所以除非B的开头i=1，答案为0，否则B的开头越后，答案越小

⑥这样就可以使用贪心算法，从头到尾扫一遍，找连续的不下降子序列，注意去不去等于的问题。

设开头为j，结尾为k，则其中存在k-n-j+1个连续子序列，注意不是1个，因为相邻两个数可以相同，例如：

A：1 1 1 1 1

B：1 1 1 1 1 1 1 1 1

[1] 当j=1时，直接返回答案0

[2] 当j^1时，因为满足⑤的性质，所以取当前最优答案n-(k-n+1)+1=n+n-k次操作

然后继续扫，因为可能还有更优的，我第一次就栽在这里；

最终答案就是最后一次连续子序列的答案~~~

代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int N=100001;

int n,a[N<<1],t,res=-1;

void init(void)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<n;i++) a[n+i]=a[i];
n=(t=n)*2-1;
}

void work(void)
{
int j;
for (int i=1;i<=n;i++)
{
for (j=i;j<n&&a[j]<=a[j+1];j++);
if (j-i+1>=t) if (i==1) {res=0;break;} else res=t+t-j;
i=j;
}
printf("%d\n",res);
}

int main(void)
{
init();
work();
return 0;
}

http://shadowchaser.lofter.com/post/1d04e306_5dfa38f

很简单。其实他就是个环。

假设有个合法的环。那么要让他成为一个不下降数列。唯一的解开点，就是头和尾，最大和最小的时候这地方不是不下降数列。因此咱们随便从一个地方扫下去。直到扫到不合法处。再从不合法处扫到底。如果没有新的不合法，那么这个有解的。当然直接从头到尾的肯定是合法。若2处不合法必不合法

我去，我理解错了不下降序列。把相等情况当做了-1，只拿了66分，

现在仔细一想，感觉不对，去掉了那行代码，AC！！！我擦，果然写程序要好好写啊。我都多少次死在不好好理解题目了。晕死

各位要引以为戒！

###pascal code
program P1925;
var n,i:longint;
a:array[1..100001] of int64;
ans:int64;
pd:boolean;
begin
read(n); pd:=false;
for i:=1 to n do
read(a[i]);

a[n+1]:=a[1];

for i:=1 to n-1 do
begin
if (a[i]>a[i+1]) and (pd=false) then
begin
pd:=true; ans:=i+1; break;
end;
end;

if pd=false then
begin
write('0'); exit;
end
else
begin
for i:=ans to n do
if a[i]>a[i+1] then
begin
write('-1'); exit;
end;
end;

write(n-(ans-1));
end.

测试数据 #0: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #1: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #2: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #3: Accepted, time = 31 ms, mem = 1276 KiB, score = 2
测试数据 #4: Accepted, time = 31 ms, mem = 1276 KiB, score = 2
测试数据 #5: Accepted, time = 46 ms, mem = 1272 KiB, score = 2
测试数据 #6: Accepted, time = 31 ms, mem = 1276 KiB, score = 2
测试数据 #7: Accepted, time = 15 ms, mem = 1272 KiB, score = 2
测试数据 #8: Accepted, time = 31 ms, mem = 1276 KiB, score = 2
测试数据 #9: Accepted, time = 31 ms, mem = 1272 KiB, score = 2
测试数据 #10: Accepted, time = 46 ms, mem = 1276 KiB, score = 2
测试数据 #11: Accepted, time = 15 ms, mem = 1272 KiB, score = 2
测试数据 #12: Accepted, time = 46 ms, mem = 1276 KiB, score = 2
测试数据 #13: Accepted, time = 31 ms, mem = 1276 KiB, score = 2
测试数据 #14: Accepted, time = 46 ms, mem = 1276 KiB, score = 2
测试数据 #15: Accepted, time = 31 ms, mem = 1280 KiB, score = 2
测试数据 #16: Accepted, time = 31 ms, mem = 1272 KiB, score = 2
测试数据 #17: Accepted, time = 46 ms, mem = 1276 KiB, score = 2
测试数据 #18: Accepted, time = 31 ms, mem = 1272 KiB, score = 2
测试数据 #19: Accepted, time = 46 ms, mem = 1272 KiB, score = 2
测试数据 #20: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #21: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #22: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #23: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #24: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #25: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #26: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #27: Accepted, time = 15 ms, mem = 1276 KiB, score = 2
测试数据 #28: Accepted, time = 15 ms, mem = 1272 KiB, score = 2
测试数据 #29: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #30: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #31: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #32: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #33: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #34: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #35: Accepted, time = 15 ms, mem = 1276 KiB, score = 2
测试数据 #36: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #37: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #38: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #39: Accepted, time = 15 ms, mem = 1276 KiB, score = 2
测试数据 #40: Accepted, time = 15 ms, mem = 1272 KiB, score = 2
测试数据 #41: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #42: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #43: Accepted, time = 0 ms, mem = 1272 KiB, score = 2
测试数据 #44: Accepted, time = 15 ms, mem = 1276 KiB, score = 2
测试数据 #45: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #46: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #47: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #48: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
测试数据 #49: Accepted, time = 0 ms, mem = 1276 KiB, score = 2
Accepted, time = 675 ms, mem = 1280 KiB, score = 100

思路很简单，把数组首尾相接，假定是由若干个不下降序列组成的。扫描不下降序列的断点并记录第一个断点位置，如果有a(i-1)>a(i)>a(i+1)即连续下降直接无解。如果断点数为0或1说明有解，否则无解，输出就好.O(n)

const maxn=100000;
var
n,i,t,p:longint;
a:array[0..maxn+1] of longint;
begin
readln(n); t:=0; p:=1;
for i:=1 to n do read(a[i]);
a[0]:=a[n];a[n+1]:=a[1];
for i:=1 to n do
if (a[i]<a[i-1]) and (a[i]<=a[i+1]) then
begin
inc(t);
if t=1 then p:=i else break;
end
else if (a[i-1]>a[i]) and (a[i]>a[i+1]) then
begin writeln(-1);halt end;
if t<2 then writeln((n-p+1)mod n) else writeln(-1);
end.


/*

Author : Slience_K
Belong : C++
Pro : Vijos P 1925

*/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int INF = ( int )( 1e9 );
int a[ 100005 ] , n , k , pos;
void Print( int x ){
printf( "%d" , x );
exit( 0 );
}
int main(){
freopen( "P1925.in" , "r" , stdin );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[ i ] );
a[ n + 1 ] = INF;
k = -1;
for( int i = 1 ; i <= n ; i++ )
if ( a[ i ] < a[ i - 1 ] ){
k = i;
break;
}
if ( k == -1 ) Print( 0 );
pos = -1;
for( int i = k + 1 ; i <= n ; i++ )
if ( a[ i ] < a[ i - 1 ] ){
pos = i;
break;
}
if ( pos != -1 ) Print( -1 );
if ( a[ 1 ] < a[ n ] ) Print( -1 );
Print( n - k + 1 );
return 0;
}

#数组都不需要，，，
##满足可以通过移动头部元素到尾部使其成为不下降序列时，这个串一定是由1个或2和不下降序列组成的，其中为2个不下降序列组成时，头部元素一定小于尾部元素
int n, beg;
scanf("%d%d", &n, &beg);
int m = n;
bool o = 0;
int last = beg;
for (int i = 1; i < n; ++i) {
int t;
scanf("%d", &t);
if (t < last) {
if (!o) {
// printf("last=%d,now number is %d",last,t);
o = 1;
m = i;
} else {
printf("-1");
return 0;
}
}
last = t;
}
#然后判断
if (o && last > beg)
printf("-1");
else
printf("%d", n - m);
return 0;