Amortised analysis of a simple loop and 3 operations I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. 

Operation OP(S,X[i]) has complexity O(log|S|) and operations push and pop has constant complexity O(1).

S &lt;- Emptystack
for i=1 to n do
    while (S!=0) and OP(S,X[i]) do
        pop(S)
    od
    push(S,X[i])
od


I would like to proove it using potential function. It would be simple if there were just pop(S) and push(s):

Pot.function represents number of items in stack


  C^ PUSH = 1 + |S|+1 - |S| = 2  
  
  C^ POP = 1 + |S|-1 - |S| = 0


So the complexity would be linear (O(2n)) = O(n). But I don't know how to compute amortized complexity of OP.
We can divide the running time into several parts:


Pushes.
Pops.
The first OP performed at every round.
Subsequent OPs performed at every round.


Note that every OP costs $O(\log n)$, that there are at most $n$ pops, and that each "subsequent OP" follows a pop. We conclude that the total running time of pushes and pops is $O(n)$, the total running time of first OPs is $O(n\log n)$ (since there are $n$ rounds), and the total running time of subsequent OPs is $O(n\log n)$ (since there are at most $n$ pops). In total, the running time is $O(n\log n)$.

If you want to use the potential method, try to use a potential of the form $|S| + \log(|S|!)$.