Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from heapq import heapify, heappop, heappush


N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)


def isPossible(i):
    i = A.index(A[i])
    if i < P:
        return True
    numVotes = V
    score = A[i] + M
    numVotes -= 1
    if A[P - 1] > score:
        return False
    numVotes -= P - 1
    numVotes -= N - i - 1
    if numVotes:
        heap = A[P - 1 : i][::-1]
        for j in range(M):
            temp = []
            for k in range(numVotes):
                temp.append(heappop(heap))
            for x in temp:
                heappush(heap, x + 1)
        return max(heap) <= score
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    print(lo + 1)


### FIXED CODE ###

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)


def isPossible(i):
    # Get highest rank with the same score
    i = A.index(A[i])

    # If already high rank, can vote top V to keep relative ordering
    if i < P:
        return True

    numVotes = V
    # Otherwise have every judge vote for i-th first
    # Each judge has V - 1 votes remaining
    score = A[i] + M
    numVotes -= 1
    # This is the best possible rank (more voting can only decrease rank)
    # If it isn't good enough, return early
    if A[P - 1] > score:
        return False
    # Soak up votes by voting for everything after i-th
    # Since adding M to everything, they will still be smaller
    numVotes -= N - i - 1
    # Soak up more votes by voting for everything in the top P - 1
    # Our element just needs to be within top P even if it's last
    numVotes -= P - 1
    if numVotes > 0:
        # If there are any votes remaining, it will be for indices P-1 thru i-1
        # We currently have:
        # A[i] + M >= A[P-1] >= A[P-2] >= ... >= A[i - 1] > A[i]
        # We want to distribute the remaining votes so that none of these become
        # greater than A[i] + M
        remainingVotes = numVotes * M
        gap = sum(score - x for x in A[P - 1 : i])
        return gap >= remainingVotes
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    # If i-th is possible, so is 0th to (i-1)th
    # So binary search for the last index possible
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    # If index i is possible, there are i+1 possible problems
    print(lo + 1)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

visited = [0]
steps = 0

while steps<N:
  curr_i = visited[-1]
  curr_val = A[curr_i]
  if curr_i == 1:
    print(steps)
    exit()
  else:
    next_i = curr_val - 1
    if next_i in visited:
      print(-1)
      exit()
    else:
      steps+=1
      visited.append(curr_val -1)
print(-1)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

visited = [0]
steps = 0

while steps<N:
  curr_i = visited[-1]
  curr_val = A[curr_i]
  if curr_i == 1:
    print(steps)
    exit()
  else:
    steps+=1
    visited.append(curr_val -1)
print(-1)
### BUGGY CODE ###

import collections
import math
import copy

H,W=map(int,input().split())

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]


while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])

nax=0
for i in range(H):
    for j in range(W):
        nax=max(nax,d[i][j])
print(nax)

### FIXED CODE ###

import collections
import math
import copy

H,W=map(int,input().split())

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]

nax=0
while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            nax=max(nax,d[ny][nx])
            queue.append([ny,nx])


print(nax)
### BUGGY CODE ###

from heapq import heapify, heappush, heappop

def max2(x, y): return x if x >= y else y

def solve(As, Bs):
    for A, B in zip(As, Bs):
        if A > B:
            return -1

    PQ = [(-B, i) for i, (A, B) in enumerate(zip(As, Bs)) if A != B]
    heapify(PQ)
    ans = 0
    while PQ:
        B, i = heappop(PQ)
        A, B = As[i], -B
        sumNeib = Bs[i-1] + Bs[(i+1)%N]

        if B <= sumNeib or B-sumNeib < A:
            return -1
        num = (B - max2(A, sumNeib)) // sumNeib
        B -= sumNeib * num
        if B-sumNeib >= A:
            B -= sumNeib
            num += 1

        if A != B:
            heappush(PQ, (-B, i))
        Bs[i] = B
        ans += num

    return ans


N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

ans = solve(As, Bs)
print(ans)


### FIXED CODE ###

from heapq import heapify, heappush, heappop

def max2(x, y): return x if x >= y else y

def solve(As, Bs):
    for A, B in zip(As, Bs):
        if A > B:
            return -1

    PQ = [(-B, i) for i, (A, B) in enumerate(zip(As, Bs)) if A != B]
    heapify(PQ)
    ans = 0
    while PQ:
        B, i = heappop(PQ)
        A, B = As[i], -B
        sumNeib = Bs[i-1] + Bs[(i+1)%N]

        if B <= sumNeib or B-sumNeib < A:
            return -1
        num = (B - max2(A, sumNeib)) // sumNeib
        B -= sumNeib * num
        if B-sumNeib >= A:
            B -= sumNeib
            num += 1

        if A != B:
            heappush(PQ, (-B, i))
        Bs[i] = B
        ans += num

    return ans


N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

ans = solve(As, Bs)
print(ans)
### BUGGY CODE ###

N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]

s = [0] * (len(a) + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

ans = 0
for l in range(len(a)):
    for r in range(l + 1, len(a) + 1):
        ans += s[r] - s[l] == 0
print(ans)



### FIXED CODE ###

from collections import Counter

N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]

s = [0] * (len(a) + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

c = Counter()

for i in range(len(s)):
    c[s[i]] += 1

ans = 0
for cnt in c.values():
    if cnt < 2: continue

    ans += (cnt * (cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if not _p in s and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if not _p in s and 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
r,g,b = sorted((r,g,b), reverse=True)
for x in range( math.ceil((n / r)) + 1):
    for y in range( math.ceil( (n - (r*x) ) / g) + 1):
        for z in range(math.ceil((n - (r * x) - (g * y)) + 1)):
            if (n - (r * x) - (g * y) - (b * z) ) == 0:
                count = count + 1
print(count)

### FIXED CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
r,g,b = sorted((r,g,b), reverse=True)
for x in range( math.ceil((n / r)) + 1):
    for y in range( math.ceil( (n - (r*x) ) / g) + 1):
        if (n - (r*x) - (y*g)) < 0:
            break
        if ((n - (r*x) - (g * y)) % b) == 0:
            count = count + 1
print(count)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
dp = [inf for _ in range(n + 1)] #i手で到達できる場所
dp[0] = 0
arr = [[inf for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    arr.append(0)
    if s[i] == 0:
        for j in reversed(range(1, m + 1)):
            if 0 <= i - j <= n and s[i - j] == 0 and dp[i] >= dp[i - j] + 1:
                dp[i] = dp[i - j] + 1
                arr[i][dp[i - j] + 1] = j
                break
ans = [inf for _ in range(dp[n])]
idx = n
for i in reversed(range(1, dp[n] + 1)):
    ans[i - 1] = arr[idx][i]
    idx -= arr[idx][i]
for i in range(dp[n]):
    ans[i] = str(ans[i])
print(' '.join(ans))


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
ans = []
hr = n
while hr > 0:
    for i in reversed(range(1, m + 1)):
        if 0 <= hr - i <= n and s[hr - i] == 0:
            ans.append(i)
            hr -= i
            break
ans = list(reversed(ans))
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(' '.join(ans))
### BUGGY CODE ###

import sys

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

for y in t:
    if y not in s:
        print(-1)
        sys.exit()

suffix = 0
idx = 0
ten = 0
for z in t:
    idx = min([m for m in cnt[z] if m>=idx]) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

### FIXED CODE ###

import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0
#print(cnt)
for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    #print(idx, z, ten)

suffix = idx + ten * n

print(suffix)
### BUGGY CODE ###

import math
import copy
m=int(input())
a=list(map(int,input().split()))
total=0
count=0
for j in range(m):
   c = a.count(j+1)
   if c>1:
      count = math.factorial(c)//math.factorial(2)//math.factorial(c-2)
      total = total + count
      count=0
for k in range(m):
    c = a.count(a[k])
    d=total
    if c > 2:
        d =d - math.factorial(c)//math.factorial(2)//math.factorial(c-2)+math.factorial(c-1)//math.factorial(2)//math.factorial(c-3)
    if c==2:
        d= d-1
    print(d)


### FIXED CODE ###

import math
import collections
m=int(input())
a=list(map(int,input().split()))
A=collections.Counter(a)
total=0
for j in A.values():
    total = total + j*(j-1)//2
for k in range(m):
    s=A[a[k]]
    d=total-s+1
    print(d)
### BUGGY CODE ###

import sys
n, k = list(map(int, sys.stdin.readline().split()))
arr = list(map(int, sys.stdin.readline().split()))
 
dp = [100000000000] * n
 
dp[0] = 0
dp[1] = dp[0] + abs(arr[1] - arr[0])
 
for i in range(2, len(arr)):
	for j in range(1, k + 1):
		if (i - j < 0): continue
		dp[i] = min(dp[i - j] + abs(arr[i - j] - arr[i]), dp[i])
 
print(dp[len(arr) - 1])

### FIXED CODE ###

import sys
n, k = list(map(int, sys.stdin.readline().split()))
arr = list(map(int, sys.stdin.readline().split()))

dp = [100000000000] * n

dp[0] = 0
dp[1] = dp[0] + abs(arr[1] - arr[0])

for i in range(2, len(arr)):
	for j in range(1, k + 1):
		if (i - j < 0): continue
		dp[i] = min(dp[i - j] + abs(arr[i - j] - arr[i]), dp[i])

print(dp[len(arr) - 1])
### BUGGY CODE ###

from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = -(1e9 + 5)
for i in range(N):
    x = i
    S = deque()
    s = 0
    while True:
        x = P[x] - 1
        S.append(C[x])
        s += C[x]
        if x == i:
            break
    l = len(S)
    a = 0
    for i in range(l):
        a += S[i]
        if i + 1 > K:
            break
        An = a
        if s > 0:
            An += s * ((K - i - 1) // l)
        A = max(A, An)
print(A)

### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = -(1e9 + 5)
for i in range(N):
    x = i
    S = deque()
    s = 0
    while True:
        x = P[x] - 1
        S.append(C[x])
        s += C[x]
        if x == i:
            break
    l = len(S)
    a = 0
    for i in range(l):
        a += S[i]
        if i + 1 > K:
            break
        An = a
        if s > 0:
            An += s * ((K - i - 1) // l)
        A = max(A, An)
print(A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

road_h = [[0 for i in range(6)] for j in range(7)] #?¨??????????
road_v = [[0 for i in range(7)] for j in range(6)] #????????????
ax = ay = 1
ad_list = ['L', 'R', 'U', 'D']

for i in range(9):
    line = str(raw_input())
    if i % 2 == 0:
        for j in range(4):
            if line[j] == '1':
                road_h[1+i/2][1+j] += 1
    else:
        for j in range(5):
            if line[j] == '1':
                road_v[1+i/2][1+j] += 1

ad = 1
ax += 1
ans = 'R'
while True:
    if ax == 1 and ay == 1:
        break
    if ad == 0:     #?????????
        if road_v[ay][ax]:
            ay += 1
            ad = 3
        elif road_h[ay][ax-1]:
            ax -= 1
        elif road_v[ay-1][ax]:
            ay -= 1
            ad = 2
    elif ad == 1:   #?????????
        if road_v[ay-1][ax]:
            ay -= 1
            ad = 2
        elif road_h[ay][ax]:
            ax += 1
        elif road_v[ay][ax]:
            ay += 1
            ad = 3
    elif ad == 2:   #?????????
        if road_h[ay][ax-1]:
            ax -= 1
            ad = 0
        elif road_v[ay-1][ax]:
            ay -= 1
        elif road_h[ay][ax]:
            ax += 1
            ad = 1
    elif ad == 3:   #?????????
        if road_h[ay][ax]:
            ax += 1
            ad = 1
        elif road_v[ay][ax]:
            ay += 1
        elif road_h[ay][ax-1]:
            ax -= 1
            ad = 0
    ans = ans + ad_list[ad]
print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-

road_h = [[0 for i in range(6)] for j in range(7)] #?¨??????????
road_v = [[0 for i in range(7)] for j in range(6)] #????????????
ax = ay = 1
ad_list = ['L', 'R', 'U', 'D']

for i in range(9):
    line = str(raw_input())
    if i % 2 == 0:
        for j in range(4):
            if line[j] == '1':
                road_h[1+i/2][1+j] += 1
    else:
        for j in range(5):
            if line[j] == '1':
                road_v[1+i/2][1+j] += 1

ad = 1
ax += 1
ans = 'R'
while True:
    if ax == 1 and ay == 1:
        break
    if ad == 0:     #?????????
        if road_v[ay][ax]:
            ay += 1
            ad = 3
        elif road_h[ay][ax-1]:
            ax -= 1
        elif road_v[ay-1][ax]:
            ay -= 1
            ad = 2
        else:
            ax += 1
            ad = 1
    elif ad == 1:   #?????????
        if road_v[ay-1][ax]:
            ay -= 1
            ad = 2
        elif road_h[ay][ax]:
            ax += 1
        elif road_v[ay][ax]:
            ay += 1
            ad = 3
        else:
            ax -= 1
            ad = 0
    elif ad == 2:   #?????????
        if road_h[ay][ax-1]:
            ax -= 1
            ad = 0
        elif road_v[ay-1][ax]:
            ay -= 1
        elif road_h[ay][ax]:
            ax += 1
            ad = 1
        else:
            ay += 1
            ad = 3
    elif ad == 3:   #?????????
        if road_h[ay][ax]:
            ax += 1
            ad = 1
        elif road_v[ay][ax]:
            ay += 1
        elif road_h[ay][ax-1]:
            ax -= 1
            ad = 0
        else:
            ay -= 1
            ad = 2
    ans = ans + ad_list[ad]
print ans
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}

ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0
for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

for i in range(q):
    print(ans[i])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

print("\n".join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

print(ans)