Single Pass O(N) Time, O(1) Space Solution


#1
int sum=0;
int prev = 0;
int i=0;
int n = A.size();
A.push_back(INT_MAX);
while(i<n){
    if(A[i]<A[i+1]){
        sum+=prev+1;
        prev++;
        i++;
    }else if(A[i]>A[i+1]){
        int cnt=0;
        while(i<n && A[i]>A[i+1]){
            cnt++;
            i++;
        }
        sum+= max(prev+1,cnt+1);
        sum+= (cnt*(cnt+1))/2 ;
        if(A[i]==A[i+1])
            prev=0;
        else
            prev=1;
        i++;
    }
    else{
        sum+=prev+1;
        prev=0;
        i++;
    }
}
return sum;