PROTEIN - EDITORIAL

editorial
,
1

PROBLEM LINK: CodeChef: Practical coding for everyone
DIFFICULTY: Easy
PREREQUISITES: Difference Array, Brute-Force
EXPLANATION:
For all x and y, we can update the value in map(mp) as
mp[x]+=1;
mp[y+1]-=1;
So in such a way, We can create the segments.
Now we just have to add after sorting the map based on keys.

SOLUTION:
(Python 3)

t=int(input())
for i in range(t):
    n,q=map(int,input().split())
    d={0:0}
    a=list(map(int,input().split()))
    for j in range(q):
        l,r=map(int,input().split())
        d[l]=d.get(l,0) + 1
        d[r+1]=d.get(r+1,0) - 1
    ma=-10**12
    s=0
    for i in sorted(d):
       d[i]+=s
       s=d[i]
       if d[i]>ma:
           ans=i
           ma=d[i]
    print(a[ans-1])