atcoder.jpThere are several solutions. If we may use wavelet matrix, this task becomes very easy. This method works in the online version, that is, we can reply the answer efficiently if we can't know the next query before do the previous …