カエル \(i\) が鳴いたときに共鳴する左端と右端カエル \(L_i, R_i\) を二分探索で求める.

区間 \([i, j]\) のカエルが鳴いたとき, 共鳴するカエルは区間 \([\min_{i \leq k \leq j} L_k, \max_{i \leq k \leq j} R_k]\) のカエルである. \(\min, \max\) は \(L_i, R_i\) をそれぞれ Sparse Table に乗せておけばいい.

区間 \([K, K]\) から始めて共鳴するカエルを追っていき, 区間が伸びなくなるまで続ける.