Description

战争期间，双方互打信息战，我军准备去敌方一条战斗主线上的信息塔窃取他们的信息。敌方的信息塔排成了一条线，每个信息塔都会同时向两侧(两端的塔只向一侧)严格比自己高的最近的信息塔传送信息。现在时间紧迫，我们只能去其中一个信息塔，为了最高效的窃取敌人的信息，我们必须选择其中信息接收量最大的塔。现在请你去执行这个窃取任务。

 

Input

第1行，一个整数N(1<=N<=50000)，表示这条线上有多少个信息塔。

第2行，N个整数h1到hn，其中hi(1<=hi<=2000000)表示第i个塔的高度。

 

Output

仅1行，一个整数i表示信息接收量最大的塔的编号，如果有多个输出编号最小的。

 

Sample Input

45 2 6 7

 

Sample Output

3

 

思路：

用栈 分两遍扫 第一遍从左到右扫 把一个元素入栈 如果这个元素小于前一个元素 前一个元素+1 此元素入栈 否则 前一个元素出栈

同理从右往左扫一遍即可

 

参考代码：

#include 
      
       #include 
       
        using namespace std;typedef struct{	int data;	int num;	int index;}node;node tower[2000001];int main(){	int n;	cin>>n;	int i;	for(i=0;i
        
         >tower[i].data;		tower[i].num=0;		tower[i].index=i+1;	}	stack
         
           sk;	sk.push(tower[0]);	for(i=1;i
          
           sk.top().data)			sk.pop();		if(sk.empty())			sk.push(tower[i]);		else		{			tower[sk.top().index-1].num++;			sk.push(tower[i]);		}	}	while(!sk.empty())		sk.pop();	sk.push(tower[n-1]);	for(i=n-2;i>=0;i--)//从右往左扫	{		while(!sk.empty()&&tower[i].data>sk.top().data)			sk.pop();		if(sk.empty())			sk.push(tower[i]);		else		{			tower[sk.top().index-1].num++;			sk.push(tower[i]);		}	}	int max=tower[0].num,no=tower[0].index;	for(i=0;i