**【NOIP2013模拟联考15】人类基因组(genes) **
Description
L教授最近正在研究一个关于人类基因的项目，基因可以被看作一个长度为N的序列：A0,A1,…,An-1。对于这个基因序列循环移动k位之后，就可以得到一个新的基因序列为：Ak,Ak+1,…,An-1,A0,A1,…,Ak-1。当一个基因序列满足对于任意的前i（1<=i<=n）项和都满足不小于0，我们就称这个基因序列为优质基因序列。
由于L教授最近工作比较繁忙，所以找到了正在实验室闲逛的你，你的任务就是帮L教授统计出所有优质基因序列的个数。
Input
第一行一个整数n，表示基因序列的长度。
第二行n个整数，依次为A0,A1,…,An-1的值。
Output
输出仅一个整数，表示优质基因序列的个数。
Sample Input
输入1：
3
2 2 3
输入2：
5
3 -1 2 -3 4
Sample Output
输出1：
3
【样例1说明】
3个元素的序列：2 2 3，循环移动情况如下：
循环移动0位得到序列：2 2 3，前i项和分别为：2 4 7，符合条件；
循环移动1位得到序列：2 3 2，前i项和分别为：2 5 7；符合条件；
循环移动2位得到序列：3 2 2，前i项和分别为：3 5 7；符合条件；
输出2：
2
Data Constraint
对于30%的数据，满足1<=N<=5,000
对于50%的数据，满足1<=N<=10,000
对于100%的数据，满足1<=N<=1,000,000，-1,000<=Ai<=1,000
题解：
【题目分析】
把给出的序列复制两份构成：
A[0]、A[1]、…、A[n-1]、A[n]、A[n+1]、…、An+n-1
则循环移动K位后的序列就是上面序列的：A[k],A[k+1],…,A[k+n-1]。
设sum[i]=A[0]+A[1]+…+A[i]，则循环K位后序列的任意前p项的和为：sum[k+p]-sum[k-1]；
由此可知：判断环移动K位后的序列任意前p项和都不小于0，只判断最小的sum[k+p]与sum[k-1]的差大于等于0即可。
至于找最小的sum[k+p]，可以用下列数据结构之一进行优化：
1、线段树:时间复杂度O(2nlog2n);
2、优先队列:时间复杂度O(2nlog2n);
3、单调队列:时间复杂度O(2n);
标程：
var
i,j,k,l,n,m,ans,gb:longint;
a,sum,f1,f2:array[0..1000000] of longint;
begin
assign(input,'genes.in');reset(input);
assign(output,'genes.out');rewrite(output);
readln(n);
for i:=1 to n do
begin
read(a[i]);
sum[i]:=sum[i-1]+a[i];
end;
f1[1]:=1;f2[n]:=n;
for i:=2 to n do
begin
if sum[i]<sum[f1[i-1]] then
f1[i]:=i
else
f1[i]:=f1[i-1];
end;
for i:=n-1 downto 1 do
begin
if sum[i]<sum[f2[i+1]] then
f2[i]:=i
else
f2[i]:=f2[i+1];
end;
if sum[f1[n]]>=0 then inc(ans);
for i:=2 to n do
begin
if (sum[f2[i]]-sum[i-1]>=0) and (sum[f1[i-1]]-sum[i-1]+sum[n]>=0) then inc(ans);
end;
writeln(ans);
end.