the-amazing-race-1

As the Formula One Grand Prix was approaching, the officials decided to make the races a little more interesting with a new set of rules.
According to the new set of rules, each driver will be given a vehicle with different height and the driver with maximum SIGHT would win the race.

Now, SIGHT of a driver is defined by ( X * P ) % 1000000007, where

X = number of drivers he can see in front of him + number of drivers he can see behind him
P = position of the driver in a given scenario ( index of the driver  array is 1-N indexed )

As all the drivers are moving in a straight line, a driver i cannot see beyond another driver j if height of  j ≥ height of driver i.

INPUT
First line of the input contains t, the number of test cases. The 1st line of each test case consists of a single integer n, the number of drivers. Second line contains n space separated integers H[1], H[2], H[3]...H[n] denoting the heights of the drivers 1, 2, 3....n.

OUTPUT
Output for each test case should be a single line displaying the index of the winning driver. 
In case of ties, display the driver with minimum index.

CONSTRAINTS
0 ≤  t   ≤ 50
1 ≤  n   ≤ 10 ^ 5
 0 ≤ H[i] ≤ 10 ^ 6 

SAMPLE INPUT
2
5
4 1 2 1 4
5 
5 1 2 4 1

SAMPLE OUTPUT
5
4

Source: hackerearth | Difficulty: MEDIUM
Tags: Data structures

Implementation


Solutions:
t=int(input());
c=0;
while c<t:
	c+=1;
	n=int(input());
	h=input().split();
	h=[int(x) for x in h];
	d=0;
	fr={};
	ba={};
	max=0;
	w=n;
	while d<n:
		d1=d-1
		
		while d1>0 and h[d1]<h[d]:
			d1=d1-fr[d1];
			
		
		fr[d]=0 if d==0 else d-d1;
		
		d2=n-d;
		
		while d2<n-1 and h[d2]<h[n-d-1]:
			d2=d2+ba[d2];
		
		ba[n-d-1]=0 if d==0 else d2-(n-d-1);

		if d+1>n/2:
			si=((fr[d]+ba[d])*(d+1))%1000000007;
						
			if si>max:
				max=si
				w=d;

			elif si==max and d<w:
				w=d;

			si=((fr[n-d-1]+ba[n-d-1])*(n-d))%1000000007;
						
			if si>max:
				max=si
				w=n-d-1;

			elif si==max and n-d-1<w:
				w=n-d-1;
		d+=1;
		
		
		   
	print((w+1));



	
		
				
			
		
		
	


t=int(input());
c=0;
while c<t:
	c+=1;
	n=int(input());
	h=input().split();
	h=[int(x) for x in h];
	d=0;
	fr={};
	ba={};
	while d<n:
		d1=d-1
		
		while d1>0 and h[d1]<h[d]:
			d1=d1-fr[d1];
			
		
		fr[d]=0 if d==0 else d-d1;
		
		d2=n-d;
		
		while d2<n-1 and h[d2]<h[n-d-1]:
			d2=d2+ba[d2];
		
		ba[n-d-1]=0 if d==0 else d2-(n-d-1);

		d+=1;
		
	d=0;
	max=0;
	w=n;
	while d<n:
		si=((fr[d]+ba[d])*(d+1))%1000000007;
						
		if si>max:
			max=si
			w=d;

		elif si==max and d<w:
			w=d;
		d+=1;
		
	print((w+1));



	
		
				
			
		
		
	


t=int(input());
c=0;
while c<t:
	c+=1;
	n=int(input());
	h=input().split();
	h=[int(x) for x in h];
	d=0;
	fr={};
	ba={};
	while d<n:
		d1=d-1
		
		while d1>0 and h[d1]<h[d]:
			d1=d1-fr[d1];
			
		
		fr[d]=0 if d==0 else d-d1;
		
		d2=n-d;
		
		while d2<n-1 and h[d2]<h[n-d-1]:
			d2=d2+ba[d2];
		
		ba[n-d-1]=0 if d==0 else d2-(n-d-1);
 
		d+=1;
		
	d=0;
	max=0;
	w=n;
	while d<n:
		si=((fr[d]+ba[d])*(d+1))%1000000007;
						
		if si>max:
			max=si
			w=d;
 
		elif si==max and d<w:
			w=d;
		d+=1;
		
	print((w+1));