Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())

BIT = [0]*(N+1)　#BITを使う

def BIT_query(idx):　#idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):　#idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))　#1-indexedで扱う
lastAppeared = [-1]*(N+1)　#その色が最後に現れた位置
ans = [0]*Q　
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)　#tupleのソートは遅いので6桁区切りでintにする
queries.sort()　#rでソートされる

curR = 0　#右端の位置
for i in range(Q):
    query = queries[i]
    r = query//10**12
    l = (query//10**6)%(10**6)
    q = query % 10**6
    while curR < r:
        curR += 1
        color = c[curR]
        last = lastAppeared[color]　
        if last != -1:
            BIT_update(last,-1) #すでに現れているなら前に現れた位置から-1
        lastAppeared[color] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1) #クエリを先読みしているのでansに格納
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,readline().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    for R in range(curR+1,r+1):
        color = c[R]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[color] = R
        BIT_update(R,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    for R in range(curR+1,r+1):
        color = c[R]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[color] = R
        BIT_update(R,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,readline().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    for R in range(curR+1,r+1):
        color = c[R]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[color] = R
        BIT_update(R,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**15+l*10**8+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**15
    query %= 10**15
    l = query//10**8
    q = query % 10**8
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        last = lastAppeared[c[curR]]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**15+l*10**8+i)
queries.sort()
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        last = lastAppeared[c[curR]]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((r*10**15+l*10**8+i))
queries.sort()
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((r*10**15+l*10**8+i))
queries.sort()
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x:x[1])
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    l,r,i = queries[j]
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Fixed submission:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

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

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])