Buggy python submission (verdict: Time Limit Exceeded):
# Mo's algorithm
# 行ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline

n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size + 1)]
lmax = 0
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))
    lmax = max(lmax, l)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(lmax // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        ans[idx] = num


print(*ans, sep="\n")


Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
# Mo's algorithm
# 言ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size + 1)]
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))

# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(n // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # print(nl, nr, l, r)
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        # print("a", num, "idx", idx, "LR", (l, r))
        # print("c", count)
        ans[idx] = num


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Runtime Error):
# Mo's algorithm
# 言ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size)]
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))

# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(n // bucket_size):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # print(nl, nr, l, r)
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        # print("a", num, "idx", idx, "LR", (l, r))
        # print("c", count)
        ans[idx] = num


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        nl += l
        nr += l
        num = 0
        count = [0] * (n + 1)
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num
    preb = b


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        nl += l
        nr += l
        num = 0
        count = [0] * (n + 1)
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        num = 0
        count = [0] * (n + 1)
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
for i in range(q):
    _, r, l, idx = LR[i]
    l -= 1
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num


print(*ans, sep="\n")



Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


num = 2 ** ((n - 1).bit_length())
SEG = [0] * (2 * num)


def func(a, b):
    return a | b


for idx, val in enumerate(C):
    idx += num
    SEG[idx] = 1 << (val - 1)
for idx in range(num - 1, 0, -1):
    while idx > 0:
        SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])
        idx //= 2


def query(left, right):
    resleft = 0
    resright = 0
    left += num
    right += num
    while right - left > 0:
        if left % 2 == 1:
            resleft = func(resleft, SEG[left])
            left += 1
        if right % 2 == 1:
            right -= 1
            resright = func(resright, SEG[right])
        left //= 2
        right //= 2
    return func(resleft, resright)


for _ in range(q):
    l, r = map(int, input().split())
    temp = query(l - 1, r)
    print(popcnt(temp))


Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


num = 2 ** ((n - 1).bit_length())
SEG = [0] * (2 * num)


def func(a, b):
    return a | b


for idx, val in enumerate(C):
    idx += num
    SEG[idx] = 1 << (val - 1)
    while idx > 0:
        idx //= 2
        SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])


def query(left, right):
    resleft = 0
    resright = 0
    left += num
    right += num
    while right - left > 0:
        if left % 2 == 1:
            resleft = func(resleft, SEG[left])
            left += 1
        if right % 2 == 1:
            right -= 1
            resright = func(resright, SEG[right])
        left //= 2
        right //= 2
    return func(resleft, resright)


for _ in range(q):
    l, r = map(int, input().split())
    temp = query(l - 1, r)
    print(popcnt(temp))


Fixed submission:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")