Hello all,

This is my first blog entry on Codeforces. So please forgive me if I am not following any regulation. I recently came across a question.Its statement goes like this:

Given an array A1,A2...AN. We are asked to count the number of contiguous subarrays Ai,Ai+1...Aj such that 1≤i≤j≤N and the largest element of that subarray occurs only once in that subarray.

For example: If N=3 A[3]={1 2 3} => Ans=6 If N=4 A[4]={2 2 1 2} => Ans=6

Constraint: 1<=N<=10^5 and 1<=A[i]<=10^5

I have the Naive approach which works in O(n^2) but as evident from constraints it would give TLE. So please help to optimize the solution. Thanks.