1. Modification of a deque, which allows to find a min element in O(1).
2. Segment tree.
3. Min/max heap (was too slow for me).
4. Sparse table.
5. Sqrt decomposition.
Hope, it helps to understand how to solve this task.

Edited by author 28.02.2017 15:25