Srikant And The Game

Srikant is playing a game with his son Atharv. Initially Atharv has an array of size $N$. i.e $arr[0 ... N-1]$.Srikant has $Q$ queries. Each query consists of two integers $i$ and $j$. For each query Atharv has to report the majority element of the subarray from index $i$ to index $j$. The majority element of the subarray is the element that appears more than $\left \lfloor{n/2}\right \rfloo