[SPOJ] AEB52

Let c[i] = (#occurences of i) - 1, for i=1..n
The sequence is valid iff:
c[i] + c[i+1] + ... + c[n] >= 0 for all i=1..n <=> min(c[i] + c[i+1] + ... + c[n]) >= 0

Use an interval tree to represent c[i] and query: t=min(c[i] + c[i+1] + ... + c[n])