In this HackerEarth The Amazing Race problem solution 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 a different height and the driver with maximum SIGHT would win the race.

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

1. X = number of drivers he can see in front of him + number of drivers he can see behind him
2. 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.

## HackerEarth The Amazing Race problem solution.

`#include<iostream>#include<cstdio>#include<vector>#include<cstdlib>#include<algorithm>#include<climits>#include<cstring>#include<set>#include<stack>using namespace std;#define MOD 1000000007int main(){    int t, n;    vector <int> H;    cin>>t;    while(t--)    {        scanf("%d",&n);        H.resize(n+1);        for(int i = 1 ; i <= n ; i++)        {            scanf("%d",&H[i]);        }        vector <int> rear(n+1);        stack<int> str;        str.push(1);        rear = 0;        for(int i = 2; i <= n ; i++)        {                while( (str.size() > 0) && ( H[ str.top() ] < H[i]) )                {                    str.pop();                }                if( str.size() > 0 )                {                    rear[i] = i - str.top();                }                else                    rear[i] = i - 1;                str.push(i);        }        vector <int> front(n+1);        stack<int> stf;        stf.push(n);        front[n] = 0;        for(int i = n; i >= 1 ; i--)        {                while( (stf.size() > 0) && ( H[ stf.top() ] < H[i] ) )                {                    stf.pop();                }                if( stf.size() > 0 )                {                    front[i] =  stf.top() - i;                }                else                    front[i] = n-i;                stf.push(i);        }        long long x , p, sight = -1,ans ;        for(int i = 1; i<= n ; i++)        {            x = front[i]+rear[i];            p = i;            x = (x * p) % MOD;            if(sight < x)            {                sight = x;                ans = i;            }        }        printf("%lld\n",ans);    }    return 0;}`

### Second solution

`#include <cstdio>#include <cassert>using namespace std;#define MAX 100010#define INF 1000000000#define MOD 1000000007int H[MAX], X[MAX], P[MAX], left[MAX], right[MAX];int main(){    int T, N, temp;    scanf("%d", &T);    assert(T>0 and T<=50);    while(T--){        scanf("%d", &N);        assert(N>0 and N<=100000);        for(int i=1;i<=N;i++){            scanf("%d", &H[i]);            assert(H[i]>=0 and H[i]<=1000000);        }        H = INF;        left = 0;        left = 0;        X = 0;        temp = H;        H = INF;        for(int i=2;i<=N;i++){            if(H[i]<=H[i-1]){                X[i] = 1;                left[i] = i-1;            }else{                int j = i-1;                while(H[j]<H[i]){                    j = left[j];                }                left[i] = j;                X[i] = i-j;            }        }        H = temp;        H[N+1] = INF;        right[N+1] = N+1;        right[N] = N+1;        P[N] = 0;        H[N] = INF;        for(int i=N-1;i>0;i--){            if(H[i]<=H[i+1]){                P[i] = 1;                right[i] = i+1;            }else{                int j = i+1;                while(H[j]<H[i]){                    j = right[j];                }                right[i] = j;                P[i] = j-i;            }        }        int ans, val;        long long t;        val = -1;        for(int i=1;i<=N;i++){            t = X[i] + P[i];            t = t*i;            t = t%MOD;            if(t>val){                val = t;                ans = i;            }        }        printf("%d\n", ans);    }    return 0;}`