Problem statement : Given an array of integers A of size N. An array is called power array if floor(maximum of array/2) >= all other elements of array. E.g [5,3,6,13] is a power array since 13/2 >= 5,3,6. Calculate how many subarrays of A are Power Arrays. Note : Single element can never be a power array.Constraints : 1<=N<=10^5 , 1<=A[i]<=10^5 .

I can think of a O(n^2) solution but it will definitely timeout. Any efficient solution? P.S : It's from a contest which has ended!