# Find Maximum Index Product

You are given a list of n numbers a1,a2,…,an. For each i (1≤i≤n), define LEFT(i) to be the nearest index j before i such that aj>ai. Note that if j does not exist, we should consider LEFT(i) to be 0. Similarly, define RIGHT(i) to be the nearest index j after i such that aj>ai. Note that if j does not exist, we should consider RIGHT(i) to be 0.

Define INDEXPRODUCT(i) as the product of LEFT(i) and RIGHT(i). Find the maximum INDEXPRODUCT(i) among all 1≤i≤n.

Input Format

The first line contains an integer n, the number of integers. The next line contains the N integers.

Constraints:

1≤N≤105

Each of the N integers will range from 0 to 109

Output Format

Output the maximum INDEXPRODUCT among all indices from 1 to N.

Sample Input

5
5 4 3 4 5

Sample Output

8

Explanation

We can compute the following:

INDEXPRODUCT(1)=0
INDEXPRODUCT(2)=1×5=5
INDEXPRODUCT(3)=2×4=8
INDEXPRODUCT(4)=1×5=5
INDEXPRODUCT(5)=0

The largest of these is 8, so it is the answer

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
long int n,arr[100000],i,l,r;
long long int max=0,max_p=0;
scanf("%ld",&n);
for(i=0;i<n;i++)
{
scanf("%ld",&arr[i]);
}
for(i=1;i<(n-1);i++)
{
l=i-1;
while(l>=0)
{
if(arr[l]>arr[i])
break;
l--;
}
if(arr[l]>arr[i])
l = l+1;
else
l=0;
r=i+1;
while(r<n)
{
if(arr[r]>arr[i])
break;
r++;
}
if(r==n)
r=0;
else
r=r+1;
max_p = l*r;
if(max_p>max)
max=max_p;
}
printf("%lld",max);
return 0;
}
```

Compile & Run : https://ideone.com/so4aiz