Buggy python submission (verdict: Runtime Error):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+2)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * N

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Runtime Error):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

div = max(int(Q**.5), 1)
B = N // div

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * N

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

div = max(int(Q**.5), 1)
B = N // div

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1] ^ -(v[0]//B & 1)))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

print('\n'.join(map(str, ans)))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

B = max(1, int(N**.5))

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1] ^ -(v[0]//B & 1)))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

print('\n'.join(map(str, ans)))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

B = max(1, int(N**.5))

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1]))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

print('\n'.join(map(str, ans)))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

N, Q = map(int, input().split())
C = list(map(int, input().split()))

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

print('\n'.join(map(str, ans)))