Segtree is obviously overkill here and not the best solution. It works pretty fast with sliding window for linear time.