Create a new array in which we store 1 if a [ i ] > k otherwise we store - 1.
for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] > k ) : NEW_LINE INDENT pre [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT pre [ i ] = - 1 NEW_LINE DEDENT DEDENT