You can solve it in NlogN about the same way you solve it in Nlog^2. You keep a segment tree with the maximum on each segment, and then when you need a certain position you can instead of binary searching it, go directly to it through the intern structure of the segment tree. For example, let's consider how the interval [i, N] is decomposed in at most logN intervals maintained in the segment tree, in order of their appearance. Now, you can iterate over them: the position you're looking for is part of the first segment with a maximum value of at least how much you need (that is x). So far you had O(logN). Now all you have to do is to find the first position in this interval with value greater than x (such a position exits as the maximum would be fine — we already checked that). So you can go downwards starting from the segment, always choosing the left child if that one has a maximum of at least x, or the right one otherwise. That would be logN+logN -> O(logN) complexity for querying.

We can maintain a segment tree of maximum values and do it in . Suppose, we have to find next greater element for range [i + 1,  n - 1] for index i. Let us suppose the maximum of range [i + 1, n - 1] is less than a[i], then we don't have any next greater element and we return  - 1. Otherwise, check the left half and right half of the range [i + 1, n - 1]. If the maximum in left half is  ≥ a[i], you'll go to the left half in the query function of your segment tree, else you'll go the right half of your segment tree.
Now, how to implement this? Well, our range [i + 1, n - 1] actually consists of disjoint ranges in segment tree, so you'll go to the leftmost range which lies in our original range, check for the above conditions there. If it doesn't satisfies, we will return  - 1 and we don't have to go to further down the segment tree. If the leftmost range doesn't return  - 1, we don't have to go the other ranges which cover [i + 1, n - 1], so overall complexity is only.

Nice discussion of ongoing Codechef long contest problem