Recently, I came across this problem through the USACO Guide (thanks Benq, thecodingwizard, caoash, darren_yao, nchn27, and frodakcin for the the amazing resource!).

I know (from the guide) that the solution involves Wavelet Trees, I have no idea how to use it here (Actually, I really only understand the basic implementation).

Any hint/solution/approach is greatly appreciated.

Thanks.