Intervals and Intersections

Vivek believes that this problem is the hardest problem ever and no one can solve it. Please prove him wrong. You are given a sequence $A_1, A_2, \ldots, A_N$ and $M$ intervals $[L_1, R_1], [L_2, R_2], \ldots, [L_M, R_M]$. For any subset $S$ of these intervals: - If $S$ is non-empty, let's define $L = \mathrm{max}_{i \in S}\,(L_i)$ and $R = \mathrm{min}_{i \in S}\,(R_i)$. - The set $S$ is *disjoi