Find out the contribution of the current element in array [ 0 , i ] and update pre [ i ]
for ( int i = 1 ; i < n ; i ++ ) { if ( a [ i ] > a [ i - 1 ] ) pre [ i ] = pre [ i - 1 ] + 1 ; else pre [ i ] = 1 ; }