Harryxun/stf_run huggingface dataset:
n = int(input())
x = input()

def popcount(num):
    return num.count('1')

popc = [-1]*(n+1)
dp = [-1]*(n+1)#index=わったあまり

for i in range(1,n+1):
    now = list(x)
    if now[i-1] == '0':
        now[i-1] = "1"
    else:
        now[i-1] = "0"
    now = "".join(now)
    
    ans = 0
    hozon = int(now,2)%popcount(now)
    while True:
        """
        if popc[int(now,2)] == -1:
            popc[int(now,2)] = popcount(now)
        """
        
        amari = int(now,2)%popcount(now) 
        if dp[amari] != -1:
            ans += dp[amari]
            dp[hozon] = ans
            break
        now = amari
        ans += 1
        if now == 0:
            break
        now = bin(now)[2:]
    
    print(ans) 

### FIXED CODE ###

n = int(input())
X = input()

cnt = [0]*(200001)
for i in range(1,200001):
    pc = bin(i).count('1')
    cnt[i] = cnt[i%pc] + 1
    
plus = X.count("1")+1
minus = X.count("1")-1

defp = int(X, 2)%plus
if minus:
    defm = int(X, 2)%minus
else:
    defm = None

pl = 1
mi = 1
ans = []
for i, x in enumerate(X[::-1]):
    if x == "0":
        ans.append(cnt[(defp+pl)%plus]+1)
    else:
        if minus:
            ans.append(cnt[(defm-mi)%minus]+1)
        else:
            ans.append(0)
    pl = 2*pl%plus
    if minus:
        mi = 2*mi%minus

print(*ans[::-1], sep="\n")
import sys

def main(lines):
  line=lines[0].split()
  n = int(line[0])
  x = int(line[1])
  t = int(line[2])
  ans = math.ceil(n/x)*t
  print(ans)

if __name__ == '__main__'
    lines = []
    for l in sys.stdin
        lines.append(l.rstrip('rn'))
    main(lines)


### FIXED CODE ###

import sys
import math

def main(lines):
    line=lines.split()
    n = int(line[0])
    x = int(line[1])
    t = int(line[2])
    ans = math.ceil(n/x)*t
    print(ans)

if __name__ == '__main__':
    lines=input()
    main(lines)
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b2 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1

### FIXED CODE ###

def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1
import sys
read=sys.stdin.read
readline=sys.stdin.readline

def isinsums(x,lst):
  s=sum(lst)
  t=(s+x)//2
  if s==0 and x==0:
    return True
  if (s-x)%2 or t<0:
    return False
  t=(s+x)//2
  m1=1<<(t+1)-1
  m2=1<<t
  sums=0
  for e in lst:
    sms=(sums|(1+sums)<<e)&m1
  sms|=1
  if (sms)&m2>0:
    return True
  return False

s=readline().strip()
x,y=map(int,readline().split())

s=s.replace('TF','T F')
s=s.replace('FT','F T')
bs=s.split()
if bs[0][0]=='F':
  x-=len(bs[0])
  del bs[0]

xy=[[],[]]
f=0
for i,e in enumerate(bs):
  if not i%2:
    l=len(e)
  else:
    f^=l%2
    xy[f].append(len(e))
if isinsums(x,xy[0]) and isinsums(y,xy[1]):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

import sys
read=sys.stdin.read
readline=sys.stdin.readline

def isinsums(x,lst):
  s=sum(lst)
  t=(s+x)//2
  if s==0 and x==0:
    return True
  if (s-x)%2 or t<0:
    return False
  t=(s+x)//2
  m1=(1<<(t+1))-1
  m2=1<<t
  sums=0
  for e in lst:
    sums=(sums|(1+sums)<<e)&m1
  sums|=1
  if (sums)&m2>0:
    return True
  return False

s=readline().strip()
x,y=map(int,readline().split())

s=s.replace('TF','T F')
s=s.replace('FT','F T')
bs=s.split()
if bs[0][0]=='F':
  x-=len(bs[0])
  del bs[0]

xy=[[],[]]
f=0
for i,e in enumerate(bs):
  if not i%2:
    l=len(e)
  else:
    f^=l%2
    xy[f].append(len(e))
if isinsums(x,xy[0]) and isinsums(y,xy[1]):
  print('Yes')
else:
  print('No')
from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0 and tmp_H<=0:
                continue #????

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:
            return key,d[key]
(X,Y),H = find(Cxy)
print(X,Y,H)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
verify =[]
XYH.sort(key=lambda x:-x[2])

for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0:
                if tmp_H < Cxy[(cx,cy)]:
                    Cxy[((cx, cy))]=-1
                continue

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:

            return key,d[key]

(X,Y),H = find(Cxy)
print(X,Y,H)
input("ATCG"["TAGC".find(input())])


### FIXED CODE ###

B = input()

_dir = {"A": "T", "T": "A", "G": "C", "C": "G"}

print(_dir[B])
import numpy as np


h,w = list(map(int,input().split()))
if h == 1 or w == 1:
    print(1)
else
    print( int(np.ceil(h*w/2)))


### FIXED CODE ###

import numpy as np


h,w = list(map(int,input().split()))
if h == 1 or w == 1:
    print(1)
else:
    print( int(np.ceil(h*w/2)))
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
DIV_NUM = 1000000007


N,K = map(int, input().split())
A = [int(x) for x in input().split()]

if N==1:
    print(0)
    exit()

tree = [0] * (N+1)

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

B = sorted(A)

q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
# print(answer)
answer = answer % DIV_NUM
answer = (K * answer) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()

# https://kira000.hatenadiary.jp/entry/2019/02/23/053917
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

answer = bubble_sort(AA)

B = sorted(A)
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
#16D8101012J 伊藤惇 dj Python3 

def area(a,b):
    c=a*b
    return c

def perimeter_of_the_rectangle(a,b):
    c=(a+b)*2
    return c

def Rectangle():
    a=int(input("input_a:"))
    b=int(input("input_b:"))
    c=area(a,b)
    d=perimeter_of_the_rectangle(a,b)
    print("{} {}".format(c,d),end="")

if __name__ == '__main__':
    Rectangle()

"""
perimeter

"""


### FIXED CODE ###

def area(a,b):
    c=a*b
    return c
def perimeter_of_the_rectangle(a,b):
    c=(a+b)*2
    return c
def Rectangle():
    a,b=map(int,input().split())
    c=area(a,b)
    d=perimeter_of_the_rectangle(a,b)
    print("{} {}".format(c,d))
    
if __name__ == '__main__':
    Rectangle()
A,B,K = map(int,input().split())
if(B>A):
  A,B=B,A
divisor = [x for x in range(B,0,-1) if (A%x==0 and B%x==0)]
print(divisor[K+1])

### FIXED CODE ###

A,B,K = map(int,input().split())
d=[]
if(A>B):
    M=A
    m=B
else:
    M=B
    m=A

for x in range(m,0,-1):
    if(m%x ==0 and M%x ==0):
       d.append(x) 

print(d[K-1])
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

start_points = [0 for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] % 2 != 0:
            start_points[i] = j
            break

is_zero = [False] * H
for i in range(H):
    cnt = 0
    for j in range(W):
        if A[i][j] != 0:
            cnt += 1
    if cnt == 0:
        is_zero[i] = True

N = 0
for i in range(H):
    N += W - start_points[i] - 1

y_start = 0
while is_zero[y_start]:
    y_start += 1
N += H - y_start - 1
# N = H * (W - 1) + H - 1
print(N)
for i in range(H):
    for j in range(start_points[i], W - 1):
        print(i + 1, j + 1, i + 1, j + 2)

for i in range(y_start, H - 1):
    i += 1
    print(i, W, i + 1, W)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

path = []
for i in range(H):
    if i % 2 == 0:
        for j in range(W):
            x = (i, j)
            path.append(x)
    else:
        for j in range(W - 1, -1, -1):
            x = (i, j)
            path.append(x)

ans = []
for i in range(len(path) - 1):
    p = path[i]
    p2 = path[i + 1]
    if A[p[0]][p[1]] % 2 != 0:
        A[p2[0]][p2[1]] += 1
        ans.append((p[0] + 1, p[1] + 1, p2[0] + 1, p2[1] + 1))
print(len(ans))
for a in ans:
    print(*a)
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
p=O
for i in range(n):
  p+=b[a[i]-1]
  if i>=1 and a[i]-a[i-1]==1:
    p+=c[a[i-1]-1]
print(p)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
p=0
for i in range(n):
  p+=b[a[i]-1]
  if i>=1 and a[i]-a[i-1]==1:
    p+=c[a[i-1]-1]
print(p)
s，t = input().split()
print(t+s)

### FIXED CODE ###

s,t = input().split()
print(t+s)
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def check(node_hash_list, edge_color_hash, next_node, node, color):
    edge_color_hash[str(node) + " " + str(next_node)] = color
    edge_color_hash[str(next_node) + " " + str(node)] = color
    new_color = 1
    max_color = color
    for new_next_node in node_hash_list[next_node]:
        if new_next_node == node:
            continue
        if color == new_color:
            new_color += 1
        if max_color < new_color:
            max_color = new_color
        temp_color = check(node_hash_list, edge_color_hash, new_next_node, next_node, new_color)
        new_color += 1
        if max_color < temp_color:
            max_color = temp_color
    return max_color
n = int(input())
sys.setrecursionlimit(n * 10)
node_hash_list = {}
print_list = []
for i in range(1, n):
    input_string = input()
    print_list.append(input_string)
    a, b = map(int, input_string.split())
    if a not in node_hash_list:
        node_hash_list[a] = []
    if b not in node_hash_list:
        node_hash_list[b] = []
    node_hash_list[a].append(b)
    node_hash_list[b].append(a)
edge_color_hash = {}
node = 1
color = 0
max_color = 1
for next_node in node_hash_list[node]:
    color += 1
    if max_color < color:
        max_color = color
    temp_color = check(node_hash_list, edge_color_hash, next_node, node, color)
    if max_color < temp_color:
        max_color = temp_color

print(max_color)
for key in print_list:
    print(edge_color_hash[key])
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

MAX=float('inf')
N,M,L=map(int, raw_input().split())
Roads = [[ 0 if i == j else MAX for j in range(N)] for i in range(N)]

for i in range(M):
    f,t,c = map(int, raw_input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(raw_input())
Queries = []
for i in range(Q):
    s, t = map(int, raw_input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))


### FIXED CODE ###

# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

for i in range(M):
    f,t,c = map(int, input().split())
    if c <= L:
        RG[f-1][t-1] = c
        RG[t-1][f-1] = c

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))
import sys
S = input()

if S[0] != "A":
    print("WA")
    sys.exit()

SS = S[2:-2]
if "C" in SS:
    SS.pop("C")
    if SS.islower():
        print("AC")
    else:
        print("WA")

else:
    print("WA")

### FIXED CODE ###

import sys
S = list(input())
# S = "Atcoder"
# S = list(S)

if S[0] != "A":
    print("WA")
    sys.exit()
elif S[1].isupper():
    print("WA")
    sys.exit()
elif S[-1].isupper():
    print("WA")
    sys.exit()
elif "C" in S[2:-1]:
    S.remove("C")
    del S[0]
    S = str(S)
    if S.islower():
        print("AC")
    else:
        print("WA")
else:
    print("WA")
N, M = map(int, input().split())
A = list(map(int, input().split()))
dict = dict(zip([i for i in range(1, 10)], [2,5,5,4,5,6,3,7,6]))
INF = 10 ** (N // 2 + 1)
dp = [-INF for i in range(N + 1)]
for a in A:
    dp[dict[a]] = max(dp[dict[a]] , a)
for i in range(N + 1):
    for j in range(1, 10):
        dp[i] = max(dp[i], dp[i - j] * 10 + dp[j], dp[j] * 10 +dp[i - j])
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
dict = dict(zip([i for i in range(1, 10)], [2, 5, 5, 4, 5, 6, 3, 7, 6]))
INF = 10 ** (N // 2 + 1)
dp = [-INF for i in range(N + 21)]
for a in A:
    dp[dict[a]] = max(dp[dict[a]], a)
for i in range(N + 1):
    for j in range(1, 10):
        dp[i] = max(dp[i], dp[i - j] * 10 + dp[j], dp[j] * 10 + dp[i - j])
print(dp[N])
A = int(input())
B = int(input())
print(A*B - A - B + 1)

### FIXED CODE ###

A, B = map( int, input().split())
print(A*B - A - B + 1)
K = int(imput())
S = imput()

if len(S) <= K:
    print(S)
else:
    print(S[0: K] + '...')

### FIXED CODE ###

K = int(input())
S = input()


if len(S) <= K:
    print(S)
else:
    print(S[0: K] + '...')
a,b,x=map(int,input().split())
v=a*a*b/2
import math
k=(2*v-x)*2/(a*b)
g=2*x/(a*b)
if x<=v:
  print(math.atan(b/g)*180/math.pi)
else:
  print(math.atan(b/k)*180/math.pi)

### FIXED CODE ###

a,b,x=map(int,input().split())
v=a*a*b/2
import math
k=(2*v-x)*2/(a*a)
g=2*x/(a*b)
if x<=v:
  print(math.atan(b/g)*180/math.pi)
else:
  print(math.atan(k/a)*180/math.pi)
h,w=map(int,input().split())
ans=h*w
if h>2:
    t=[h//3*w,(h-(h//3))//2*w,(h-(h//3)+1)//2*w]
    t.sort()
ans=min(ans,t[2]-t[0])
if w>2:
    t=[w//3*h,(w-(w//3))//2*h,(w-(w//3)+1)//2*h]
    t.sort()
ans=min(ans,t[2]-t[0])
a,b=h,w
#for i in range(max(1,a//3-1),min(a//2+1,a-1)):
#    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
#    t.sort()
#    ans=min(ans,t[2]-t[0])
a,b=w,h
#for i in range(max(1,a//3-1),min(a//2+1,a-1)):
#    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
#    t.sort()
#    ans=min(ans,t[2]-t[0])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

h,w=map(int,input().split())
ans=h*w
if h*w%3==0:
    print(0)
else:
    for x,y in ((h,w),(w,h)):
        x1=x//3
        x2=(x+2)//3
        y1=y//2
        y2=(y+1)//2
        ans=min(ans,abs(y*x2-y*x1))
        t=(y*x1,y2*(x-x1),(y-y2)*(x-x1))
        ans=min(ans,max(t)-min(t))
        t=(y*x2,y2*(x-x2),(y-y2)*(x-x2))
        ans=min(ans,max(t)-min(t))
    print(ans)
a.b=map(int,input().split())
print(a*b)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        q.append(inp() + [i])
    q.sort(key=lambda e:e[-2])
    mp = {}
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if da[now] in mp:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(mp[da[now]], 1)
        ans[idx] = fw.sum(l, r)
    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

### FIXED CODE ###

from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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


            

 
 
 
 
my_main()