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

a,b = map(int,input().split())

c = list(map(int,input().split()))
for i in range(len(c)-b+1):
    k = c[i:i+b]
    if k[0] * k[-1] < 0:
        if i == 0:
            m = abs(k[0]) + k[-1] +abs(min(k[0],k[-1]))
        else:
            m = min(m,abs(k[0]) + k[-1] +abs(min(k[0],k[-1])))
    else:
        if i == 0:
            m = max(abs(k[0]),abs(k[-1]))
        else:
            m = min(m,max(abs(k[0]),abs(k[-1])))

print(m)

### FIXED CODE ###

a,b = map(int,input().split())
m = 0
c = list(map(int,input().split()))
for i in range(len(c)-b+1):
    if c[i] * c[i+b-1] < 0:
        if i == 0:
            m = abs(c[i]) + c[i+b-1] +abs(min(abs(c[i]),c[i+b-1]))
        else:
            m = min(m,abs(c[i]) + c[i+b-1] +abs(min(abs(c[i]),c[i+b-1])))
    else:
        if i == 0:
            m = max(abs(c[i]),abs(c[i+b-1]))
        else:
            m = min(m,max(abs(c[i]),abs(c[i+b-1])))

print(m)
### BUGGY CODE ###

mod = 998244353
primitive_root = 3
roots = [pow(primitive_root, (mod-1)>>i, mod) for i in range(24)]
inv_roots = [pow(root, mod-2, mod) for root in roots]

def ntt(A, n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m])%mod, (A[s+j]-A[s+j+m])*w%mod
                w *= roots[n-i]
                w %= mod

def intt(A, n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m]*w)%mod, (A[s+j]-A[s+j+m]*w)%mod
                w *= inv_roots[i+1]
                w %= mod
    inv = pow((mod+1)//2, n, mod)
    for i in range(1<<n):
        A[i] *= inv
        A[i] %= mod

def convolution(A, B):
    la = len(A)
    lb = len(B)
    deg = la + lb - 2
    n = deg.bit_length()
    N = 1<<n
    A += [0]*(N-la)
    B += [0]*(N-lb)
    ntt(A, n)
    ntt(B, n)
    A = [a*b%mod for a, b in zip(A, B)]
    intt(A, n)
    return A[:deg+1]


import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = convolution(A, B)
print(*C)

### FIXED CODE ###

mod = 998244353
primitive_root = 3
roots = [pow(primitive_root, (mod-1)>>i, mod) for i in range(24)]
inv_roots = [pow(root, mod-2, mod) for root in roots]

def ntt(A, n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m])%mod, (A[s+j]-A[s+j+m])*w%mod
                w *= roots[n-i]
                w %= mod

def intt(A, n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m]*w)%mod, (A[s+j]-A[s+j+m]*w)%mod
                w *= inv_roots[i+1]
                w %= mod
    inv = pow((mod+1)//2, n, mod)
    for i in range(1<<n):
        A[i] *= inv
        A[i] %= mod

def convolution(A, B):
    la = len(A)
    lb = len(B)
    deg = la + lb - 2
    n = deg.bit_length()
    N = 1<<n
    A += [0]*(N-la)
    B += [0]*(N-lb)
    ntt(A, n)
    ntt(B, n)
    A = [a*b%mod for a, b in zip(A, B)]
    intt(A, n)
    return A[:deg+1]


import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = convolution(A, B)
print(*C)
### BUGGY CODE ###

n = int(input())
lis = list(map(int, input().split()))
count = 0
minn = lis[0]
for i in range(n):
    newlis = lis[0:i+1]
    if  minn >= lis[i]:
        count += 1
        minn = lis[i]
print(count)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
count = 0
minn = lis[0]
minl = min(lis)
flug = 0
for i in range(n):
    if flug == 0:
        if  minn >= lis[i]:
            count += 1
            minn = lis[i]
            if minn == minl:
                count += lis[i+1:].count(minl)
                flug = 1
print(count)
### BUGGY CODE ###

s = input()
q = int(input())

reverse_flag = False
for i in range(q):
  q_list = list(input().split())
  
  if len(q_list) == 1:
    reverse_flag = not reverse_flag
    
  elif q_list[1] == '1' and (not reverse_flag):
    s = q_list[2] + s
    
  elif q_list[1] == '2' and (not reverse_flag):
    s += q_list[2]
    
  elif q_list[1] == '1' and reverse_flag:
    s += q_list[2]
    
  elif q_list[1] == '2' and reverse_flag:
    s = q_list[2] + s
    
if reverse_flag:
  print(''.join(list(reversed(s))))
else:
  print(s)

### FIXED CODE ###

s = list(input())
q = int(input())

reverse_flag = False

top = []
last = []
for i in range(q):
  q_list = list(input().split())
  
  if len(q_list) == 1:
    reverse_flag = not reverse_flag
    
  elif q_list[1] == '1' and (not reverse_flag):
    top.append(q_list[2])
    
  elif q_list[1] == '2' and (not reverse_flag):
    last.append(q_list[2])
    
  elif q_list[1] == '1' and reverse_flag:
    last.append(q_list[2])
    
  elif q_list[1] == '2' and reverse_flag:
    top.append(q_list[2])
    
if reverse_flag:
  print(''.join(reversed(last)) + ''.join(reversed(s)) + ''.join(top))
else:
  print(''.join(reversed(top)) + ''.join(s) + ''.join(last))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0

for i in range(N):
	B.append(A[i])
	if B != sorted(B) and B != sorted(B, reverse = True):
		B = [A[i]]
		cut += 1
		
print(cut + 1)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0
trend = ""

for i in range(N):
	B.append(A[i])
	if len(B) == 2 or trend == "neutral":
		if min(B) == max(B):
			trend = "neutral"
		elif A[i] == max(B):
			trend = "up"
		elif A[i] == min(B):
			trend = "down"
	elif len(B) > 2:
		if trend == "up" and A[i] < B[-2]:
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] > B[-2]:
			cut += 1
			B = [A[i]]
print(cut + 1)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
s_list = []
for _ in range(h):
    s = input()
    s_list.append(s)
d = deque()
count = 0
if s_list[0][0] == '#':
    count += 1
d.append([0, 0, count])

ans = 101
while d:
    x, y, count = d.pop()
    for xx, yy in [[1, 0], [0, 1]]:
        if (0 <= x + xx < h) & (0 <= y + yy < w):
            if (s_list[x + xx][y + yy] == '#') & (s_list[x][y] == '.'):
                d.append([x + xx, y + yy, count + 1])
            else:
                d.append([x + xx, y + yy, count])
        if (x + xx == h - 1) & (y + yy == w - 1):
            if s_list[x + xx][y + yy] == '#':
	            ans = min(ans, count + 1)
            else:
                ans = min(ans, count)
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
s_list = []
for _ in range(h):
    s = input()
    s_list.append(s)
d = deque()
count = 0
if s_list[0][0] == '#':
    count += 1
d.append([0, 0, count])

vis = [[101 for i in range(w)] for j in range(h)]
if s_list[0][0] == '.':
    vis[0][0] = 0
else:
    vis[0][0] = 1
for x in range(h):
    for y in range(w):
        for xx, yy in [[1, 0], [0, 1]]:
            if (0 <= x + xx < h) & (0 <= y + yy < w):
                if (s_list[x][y] == '.') & (s_list[x + xx][y + yy] == '#'):
                    vis[x + xx][y + yy] = min(vis[x][y] + 1, vis[x + xx][y + yy])
                else:
                    vis[x + xx][y + yy] = min(vis[x][y], vis[x + xx][y + yy])          
print(vis[-1][-1])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
s = input()
q = I()
straight = True
for i in range(q):
    A = input().split()
    if A[0] == '1':
        straight = not straight
    else:
        if straight:
            if A[1] == '1':
                s = A[2] + s
            else:
                s = s + A[2]
        else:
            if A[1] == '1':
                s = s + A[2]
            else:
                s = A[2] + s
if straight:
    print(''.join(s))
else:
    print(''.join(s[::-1]))


### FIXED CODE ###

from collections import deque
d = deque([])
ans = input()
d.append(ans)
q = int(input())
rev = True # Trueなら後ろに # Falseなら前に
for i in range(q):
    Query = list(map(str,input().split()))
    if Query[0] == '2':
        if Query[1] == '1':
            if rev:
                d.append(Query[2])
            else:
                d.appendleft(Query[2])
        elif Query[1] == '2':
            if rev:
                d.appendleft(Query[2])
            else:
                d.append(Query[2])
    else:
        rev = rev^True
output = ""
while d:
    output += d.pop()
if rev:
    print(output)
else:
    print(output[::-1])
### BUGGY CODE ###

S=int(input())
a=0
for i in range(S//500+1):
  for j in range(S//5+1):
    if i*500+j*5<=S:
      a=max(a,i*1000+j*5)
    else:
      continue
      
print(a)


### FIXED CODE ###

S=int(input())

a=S//500

b=(S-500*a)//5

c=a*1000+b*5

print(c)
### BUGGY CODE ###

K,S=map(int,input().split())
count=0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if X+Y+Z==S:
        count+=1
      else:
        continue
        
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for X in range(K,-1,-1):
  if S-X>2*K:
    break    
  for Y in range(K,-1,-1):
    if 0<=S-(X+Y)<=K:
       count+=1
    elif 0>S-(X+Y):
       continue
    else:    
       break
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
answer = [-1] * N
p = [0] * N
for i in range(N):
  count[i]  = A.count(i + 1)
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  if answer[A[i] - 1] != -1:
    p[i] = answer[A[i] - 1]
  else:
    tekito = count[A[i] - 1]
    if tekito == 2:
      s = nanimo - 1
    elif tekito == 1:
      s = nanimo
    else:
      s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
    p[i] = s
    answer[A[i] - 1] = s

for i in p:
  print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
X = int(input())
n = 1
Y = 100 ** (n-1)
while Y < X:
    n += 1
else:
    print(n)

### FIXED CODE ###

# -*- coding: utf-8 -*-
X = int(input())
n = 0
m = 100
while m < X:
    n += 1
    m += m//100 

print(n)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
a,b,n = map(int,input().split())
maxpoint = 0
for x in range(n+1):
    tmp = int((a * x) / b)  - a * int(x/b) 
    maxpoint = max(tmp,maxpoint)
print(maxpoint)



### FIXED CODE ###

from sys import stdin
input = stdin.readline
 
a,b,n = map(int,input().split())
maxpoint = 0
 
if b > n  :
    tmp = int((a * n) / b)  - a * int(n/b) 
    maxpoint = max(tmp,maxpoint)
else:
    k = int(n/b)*b -1
    maxpoint =  int((a * k) / b)  - a * int(k/b) 
    if b == 1:
        maxpoint = 0
 
print(maxpoint)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = input()
L_r = []
L_g = []
L_b = []
ans = 0
for i in range(N):
    if S[i] == "R":
        L_r.append(i)
    elif S[i] == "G":
        L_g.append(i)
    else:
        L_b.append(i)
m = min(len(L_r),len(L_g),len(L_b))
if len(L_r) == m:
    for x in L_g:
        for y in L_b:
            ans += m
            if 2*x - y in L_r:
                ans -= 1
            if 2*y - x in L_r:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_r:
                ans -= 1
elif len(L_g) == m:
    for x in L_r:
        for y in L_b:
            ans += m
            if 2*x - y in L_g:
                ans -= 1
            if 2*y - x in L_g:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_g:
                ans -= 1
else:
    for x in L_r:
        for y in L_g:
            ans += m
            if 2*x - y in L_b:
                ans -= 1
            if 2*y - x in L_b:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_b:
                ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans += r*g*b
m = 0
if N >= 3:
  for i in range(N-2):
    for j in range(i+1,N-1):
      k = 2*j-i
      if  k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        m += 1
print(ans-m)
### BUGGY CODE ###

S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = (anum[i-1]*(3**hnum[i-1]) + hnum[i-1]*(3**(hnum[i-1]-1)))%Q
        C = ((czen - cnum[i])*(3**(hzen - hnum[i])) + (hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))

### FIXED CODE ###

S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)]
#bnum = [ 0 for _ in range(L+1)]
cnum = [ 0 for _ in range(L+1)]
hnum = [ 0 for _ in range(L+1)]
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
#        bnum[i] = bnum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1

ans = 0
czen = cnum[L]
hzen = hnum[L] 
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
#        A = ((anum[i-1]*(3**hnum[i-1]))%Q + (hnum[i-1]*(3**(hnum[i-1]-1)))%Q)%Q
#        C = (((czen - cnum[i])*(3**(hzen - hnum[i])))%Q + ((hzen - hnum[i])*(3**(hzen - hnum[i]-1)))%Q)%
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(A, B+1):
    if (A <= i and i <= A+K-1) or (B-K+1<= i and i <= B):
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())

# for i in range(A, B+1):
#     if (A <= i and i <= A+K-1) or (B-K+1<= i and i <= B):
#         print(i)

S=set()

for i in range(A, min(B+1, A+K)):
    S.add(i)
for i in range(max(A, B-K+1), B+1):
    S.add(i)
for k in sorted(S):
    print(k)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=list(map(int,input().split()))
uf=UnionFind(N+1)
p=list(map(int,input().split()))
for i in range(M):
    x,y=list(map(int,input().split()))
    uf.union(x,y)
count=0
for i in range(1,N+1):
    if p[i-1] in uf.members(i):count+=1
print(count)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=list(map(int,input().split()))
uf=UnionFind(N+1)
p=list(map(int,input().split()))
for i in range(M):
    x,y=list(map(int,input().split()))
    uf.union(x,y)
count=0
for i in range(1,N+1):
    if (uf.same(p[i-1],i)):count+=1
print(count)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))

limit=10**9+7
for i in range(N):
    A[i]=A[i]%limit
ans=0
for i in range(N-1):
    ans+=(A[i]*(sum(A[i+1:])%limit))
    ans=ans%limit
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

limit=10**9+7
S=[0]
for i in range(N):
    A[i]=A[i]%limit
for i in range(1,N):
    S.append((S[i-1]+A[-i])%limit)
ans=0
for i in range(N-1):
    ans+=A[i]*S[-1-i]
    ans=ans%limit
print(ans)
### BUGGY CODE ###

s, c = map(int, input().split())

ans = 0

if 2*s >= c:
  ans = c // 2
else:
  while 2*s < c and 2*(s+1) <= c-2:
    c -= 2
    s += 1
  ans = s
  
print(ans)

### FIXED CODE ###

s, c = map(int, input().split())

ans = 0
#手持ちのSで作れる分だけSccを作る
if c <= 2*s:
  ans += c // 2
  c = c%2
  s = 0
else:
  ans += s
  c = c - 2*s
  s = 0
  


#print(s)
#print(c)
#print(ans)
#まだcが余ってたらSccを作る
if c >= 4:
  ans += c // 4
  
print(ans)
### BUGGY CODE ###

from sys import exit

import copy

# import numpy as np
from collections import deque, Counter


N, Q = map(int, input().split())
C = list(map(int, input().split()))
R = [list(map(int, input().split())) for _ in range(Q)]


tmp = Counter([])

q = [copy.deepcopy(tmp)]

for c in C:
    tmp[str(c)] += 1
    q.append(copy.deepcopy(tmp))

for r in R:
    d = q[r[1]] - q[r[0] - 1]
    print(len(d))


### FIXED CODE ###

# import numpy as np
from sys import exit, stdin
import copy
from collections import deque, Counter


class BIT:
    def __init__(self, a=0):
        self.n = a
        self.d = [0] * (a + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.d[i] += x
            i += i & (-i)

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            tmp = i[0] + 1
            while tmp:
                x += self.d[tmp]
                tmp -= tmp & (-tmp)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


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

app = [-1] * (N + 1)
ps = [[] for _ in range(N)]
for i in range(N):
    tmp = app[C[i]]
    if tmp != -1:
        ps[tmp].append(i)
    app[C[i]] = i

qs = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, stdin.readline().split())
    l -= 1
    r -= 1
    qs[l].append(copy.deepcopy([r, i]))

ans = [0] * Q
d = BIT(N)
for x in range(N - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    for p in qs[x]:
        r = p[0]
        i = p[1]
        ans[i] = (r - x + 1) - d.sum(r)

for re in ans:
    print(re)
### BUGGY CODE ###

import math

a,b = map(int,input().split())

def common_divisor(n):
  if n == 1:
    return [1]
  ret = []
  for i in range(1,math.ceil(math.sqrt(n))):
    if n%i==0:
      ret.append(i)
      ret.append(n//i)      
  return sorted(ret)

ca = common_divisor(a)
cb = common_divisor(b)

sa = set(ca)
c = sa.intersection(cb)

primes = lambda n:[i for i in range(1,n+1) if len([j for j in range(1,i+1) if i%j==0]) ==2]

sp = primes(max(c))
sp.append(1)

print(len(c.intersection(sp)))

### FIXED CODE ###

import math

a,b = map(int,input().split())

def common_divisor(n):
  if n == 1:
    return [1]
  ret = []
  for i in range(1,math.ceil(math.sqrt(n))+1):
    if n%i==0:
      ret.append(i)
      ret.append(n//i)      
  return list(set(ret))

def trial_division(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(math.ceil(math.sqrt(n))) + 1, 2):
        if n % i == 0:
            return False
    return True

ca = common_divisor(a)
cb = common_divisor(b)

sa = set(ca)
c = sa.intersection(cb)

count = 1
for ci in c:
  if trial_division(ci):
    count+=1

print(count)
### BUGGY CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))

# DP[i][j] = i回以下魔法を掛けられてj色のスライムができるとき、最初のコストの最小値
DP = [[0]*n for i in range(n)]
DP[0] = a
for i in range(n-1):
    for j in range(n):
        DP[i+1][j] = min(DP[i][j], DP[i][j-1])
ans = float("inf")
for i in range(n):
    ans = min(ans, sum(DP[i])+i*x)
print(ans)

### FIXED CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))

# 空間計算量を減らしてみる
DP = a[:]
ans = sum(DP)
for i in range(n-1):
    DP = [min(DP[j],DP[j-1]) for j in range(n)]
    ans = min(ans, sum(DP) + (i+1)*x)
print(ans)