幼儿园里专门设置了测定磁的强度的机器，因为小朋友们在磁暴发生的时候是不能到户外玩的。如果机器读出的强度超过一定限度的时候，小朋友就要回到房子里面，而不能把游戏从头到尾玩完，所以他们不喜欢这个机器。奶妈们也不喜欢，因为她们成天都要帮孩子们穿衣和脱衣。
过了一段时间，人们发现磁的强度是可以预测的，因为一段长时间的平静期和一段短时间的高峰期（被称为磁暴）交替出现。因此幼儿园对机器作出了更新。
新机器将会存储过去几个小时里面磁的强度，以及显示出那段时间里的最高强度。如果在过去的6小时内，强度都较低，则这段时间为平静期，小朋友可以到户外玩耍，否则将可能出现新的高峰期，小朋友也要待在房子里。
你的任务是编写新机器的主程序
已知 M （新机器每秒钟都要输出过去 M 秒内磁的强度的最大值）和每秒测得的磁的强度（范围在0至100000之间）。
输出新机器要显示的一个数列。第一个数字表示输入数据的第1～第M个数的最大值，第二个数字表示输入数据的第2～第M+1个数的最大值，......最后一个数字表示输入数据的最后M个数的最大值。
input：
第一行为M, 1 < M <= 14000。
以下为表示每秒测得的磁的强度的数列，一行一个，不超过25000个，以-1结束。
output：
输出新机器要显示的一个数列，一行一个数字。
input：
3
10
11
10
0
0
0
1
2
3
2
-1
output：
11
11
10
0
1
2
3
3
分析：
我用的是线段树：以每个数与它前面个数组成一个线段，并且找出两两中最大的保存下来，这样再建立一个0--N个数的二叉树就OK了，那么只需找出I--I+M-1区间中的最大值即可。
【参考程序】：
#include<iostream>
using namespace std;
struct node
{
int a,b,s;
int lc,rc;
} tree[60000];
int c[25001];
int n,m,ans,tail;
inline int find_max(int x,int y)
{
if (x>y) return x;
else return y;
}
void getmax(int now,int l,int r)
{
if (l==tree[now].a && tree[now].b==r)
{
if (tree[now].s>ans) ans=tree[now].s;
return ;
}
int mid=(tree[now].a+tree[now].b)>>1;
if (r<=mid) getmax(tree[now].lc,l,r);
else if (l>=mid) getmax(tree[now].rc,l,r);
else
{
getmax(tree[now].lc,l,mid);
getmax(tree[now].rc,mid,r);
}
}
void make_tree(int l,int r)
{
tail++;int now=tail;
tree[now].a=l;tree[now].b=r;
tree[now].lc=tree[now].rc=tree[now].s=0;
if (l+1==r) tree[now].s=find_max(c[r],c[l]);
if (l+1<r)
{
int mid=(tree[now].a+tree[now].b)>>1;
tree[now].lc=tail+1;make_tree(l,mid);
tree[now].rc=tail+1;make_tree(mid,r);
int a1=tree[now].lc,b1=tree[now].rc;
tree[now].s=find_max(tree[a1].s,tree[b1].s);
}
}
int main()
{
scanf("%d",&m);
int x;n=0;
while (scanf("%d",&x),x!=-1)
{
n++;c[n]=x;
}
tail=0;make_tree(0,n);
for (int i=1;i<=n-m+1;i++)
{
ans=-1;getmax(1,i,i+m-1);
printf("%d\n",ans);
}
return 0;
}