Good question.. i didn't see this scenario... I think the question should be modified to allow equals not just strictly greater elements. Thanks for this, I have update the question and...

ILet's say if the question comes where they don't allow equals then we can precheck the input in linear time and return -1 if all elements are equal or sorted in descending order.