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

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])


### FIXED CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

N=int(input())

X=np.array(list(map(int,input().split())))

for i in range(N):
	temp=X
	temp=np.delete(temp,i)
	med=np.median(temp)
	print(int(med))

### FIXED CODE ###

import sys
import numpy as np

N=int(input())

X=np.array(list(map(int,input().split())))
temp=X
temp=np.sort(temp,kind="quicksort")
med=temp[int(N/2)]
for i in range(N):
	if X[i]<med:
		print(med)
	else:
		print(temp[int(N/2)-1])
### BUGGY CODE ###

kami = list()
N = int(input())
for x in range(N):
  i = int(input())
  if i in kami:
    kami.remove(i)
  else:
    kami.append(i)
print(len(kami))


### FIXED CODE ###

kami = set()
N = int(input())
for x in range(N):
  i = int(input())
  if i in kami:
    kami.remove(i)
  else:
    kami.add(i)
print(len(kami))
### BUGGY CODE ###

import math

def comb(p,q):
   kumi =math.factorial(p)/(math.factorial(q)*math.factorial(p-q))
   return kumi

n = int(input())
numbers =list(map(int,input().split()))
sornum =sorted(numbers, reverse=True)

large =0
inum = 0
jmum = 0
for i in range(n-1):
   for j in range(n-i):
      a = comb(sornum[i],sornum[i+j])
      if a>=large:
         large = a
         inum = sornum[i]
         jnum =sornum[i+j]
          
print(inum,jnum)

### FIXED CODE ###

n = int(input())
numbers =list(map(int,input().split()))
sornum =sorted(numbers, reverse=True)

ans =0
d_min = sornum[0]

for i in range(n-1):
   d =abs(sornum[0]/2-sornum[i+1])
   if d<d_min:
      d_min =d
      ans = sornum[i+1]

print('{} {}'.format(sornum[0], ans))
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())

a = np.array([0]*n)
a[0] += n
b = np.array([1,0])
for i in range(1,n):
    c = n // np.size(b)
    d = n % np.size(b)
    a[1:i+1] += c
    a[0] +=c
    b = np.append(b,i+1)
    if d > 0:
        a[1:d+1] +=1
    #print(a)
print(np.sum(a[k:]))


### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())

a = np.array([0]*n,dtype ='int64')
a[0] += n
for i in range(1,n):
    c = n // (1+i)
    d = n % (1+i)
    a[1:i+1] += c
    a[0] +=c
    if d > 0:
        a[1:d+1] +=1
print(np.sum(a[k:]))
### BUGGY CODE ###

def mergeSort(num_list, left, right):
	if left + 1 < right:
		mid = (left + right) / 2
		mergeSort(num_list, left, mid)
		mergeSort(num_list, mid, right)
		merge(num_list, left, mid, right)

def merge(num_list, left, mid, right):
	global count 
	n1 = mid - left
	n2 = right - mid
	L = []
	R = []
	for i in range(n1):
		L.append(int(num_list[left + i]))
	L.append(float("inf"))
	for i in range(n2):
		R.append(int(num_list[mid + i]))
	R.append(float("inf"))
	i, j = 0, 0
	for k in range(left, right):
		if L[i] <= R[j]:
			num_list[k] = L[i]
			i += 1
			count += 1
		else:
			num_list[k] = R[j]
			j += 1
			count += 1

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
mergeSort(l, 0, n)

print " ".join(map(str, l)) 
print count

### FIXED CODE ###

def mergeSort(num_list, left, right):
	if left + 1 < right:
		mid = (left + right) / 2
		mergeSort(num_list, left, mid)
		mergeSort(num_list, mid, right)
		merge(num_list, left, mid, right)

def merge(num_list, left, mid, right):
	global count 
	L = list(num_list[left:mid])
	L.append(float("inf"))
	R = list(num_list[mid:right])
	R.append(float("inf"))
	i, j = 0, 0
	for k in range(left, right):
		if L[i] <= R[j]:
			num_list[k] = L[i]
			i += 1
			count += 1
		else:
			num_list[k] = R[j]
			j += 1
			count += 1

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
for i in range(len(l)):
	l[i] = int(l[i])
mergeSort(l, 0, n)

print " ".join(map(str, l)) 
print count
### BUGGY CODE ###

A, B, Q = map(int, input().split())
shrine = []
temple = []
for i in range(A):
    shrine.append(int(input()))
for i in range(B):
    temple.append(int(input()))

for i in range(Q):
    pos = int(input())
    nsh = [pos - shrine[i] for i in range(A)]
    ntem = [pos - temple[i] for i in range(B)]
    plusA, plusB, minusA, minusB = 2E10, 2E10, -2E10, -2E10
    for i in range(A):
        if(nsh[i]>= 0):
            plusA = min(plusA, nsh[i])
        else:
            minusA = max(minusA, nsh[i])
    for i in range(B):
        if(ntem[i]>= 0):
            plusB = min(plusB, ntem[i])
        else:
            minusB = max(minusB, ntem[i])
    lis = [max(plusA, plusB), abs(min(minusA, minusB)), abs(2*plusA-minusB), abs(2*minusA - plusB), abs(2*plusB - minusA), abs(2*minusB - plusA)]
    print(min(lis))

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10**18
shrine = [-INF] + [int(input()) for i in range(A)] + [INF]
temple = [-INF] + [int(input()) for i in range(B)] + [INF]

for i in range(Q):
    pos = int(input())
    b,d = bisect.bisect_right(shrine, pos), bisect.bisect_right(temple, pos)
    res = INF
    for S in [shrine[b-1], shrine[b]]:
        for T in [temple[d-1], temple[d]]:
            d1, d2 = abs(S-pos)+abs(T-S), abs(T-pos)+abs(S-T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

n,t = map(int,input().split())
time = [-1 for i in range(6030)]
time[0] = 0
now = 0
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[0])
for i in range(n):
    for j in range(t-1,-1,-1):
        if time[j] != -1:
            time[j+lis[i][0]] = max(time[j+lis[i][0]],time[j]+lis[i][1])
print(max(time))

### FIXED CODE ###

n,t = map(int,input().split())
time = [0 for i in range(3000)]
now = 0
ans = 0
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key=lambda x:x[0])
for i in range(n):
    for j in range(t-1,-1,-1):
        if lis[i][0] + j >= t:
            ans = max(ans,time[j]+lis[i][1])
        else:
            time[j+lis[i][0]] = max(time[j+lis[i][0]],time[j]+lis[i][1])
print(max(ans,max(time)))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if int(S[i])%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if int(S[i])%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    for i in range(l-1, -1, -1):
        temp += int(S[i])*10**(l-i-1)
        temp %= P
        data[temp] += 1
    ans = data[0]
    for item in data:
        if item > 1:
            ans += item*(item-1)//2

print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = list(map(int, list(input())))

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if S[i]%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += S[i]*pow(10, l-i-1, P)
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

print(ans)
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

que = []
que.append((ch,cw,0))

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

for x,y,c in que:
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.append((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)



### FIXED CODE ###

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(-1,0),(0,1),(1,0),(0,-1)]
dxdy1 = [(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
dxdy2 = [(-1,1),(-1,2),(-2,1),(-2,2)]
dxdy3 = [(1,1),(1,2),(2,1),(2,2)]
dxdy4 = [(1,-1),(1,-2),(2,-1),(2,-2)]
while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    state = [False]*4
    for i, (dx,dy) in enumerate(dxdy):
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            state[i] = True
            nx,ny = nx+dx, ny+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[-1] and state[0]:
        for dx,dy in dxdy1:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[0] and state[1]:
        for dx,dy in dxdy2:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[1] and state[2]:
        for dx,dy in dxdy3:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[2] and state[3]:
        for dx,dy in dxdy4:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import math
a,b,c=map(int,input().split())
d=[]
for i in range(c+1):
    n=math.floor((a*i)/b)-a*(math.floor(i/b))
    d.append(n)
d=sorted(d)
print(d[-1])

### FIXED CODE ###

import math
a,b,c=map(int,input().split())
if b>c:
    print(math.floor((a*c)/b)-a*(math.floor(c/b)))
else:
    print(math.floor((a*(b-1))/b)-a*(math.floor((b-1)/b)))
### BUGGY CODE ###

N,M= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(M)]
id = [0]*N
for i in li:
    for j in range(i[0]-1,i[1]):
        id[j]+=1
print(len([i for i,x in enumerate(id) if x==M]))

### FIXED CODE ###

N,M= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(M)]
mi=0
ma=N
for i in li:
    mi=max(mi,i[0])
    ma=min(ma,i[1])
if ma>=mi:
    print(ma-mi+1)
else:
    print(0)
### BUGGY CODE ###

N=int(input())
D={}
ans = 0
for i in range(N):
    a = str(sorted(input()))
    if a in D:
        D[a] += 1
        ans += D[a]
    else:
        D[a] = 0
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A=[]
for i in range(N):
    x= str(sorted(input()))
    A.append(x)
B=collections.Counter(A)
ans = 0
for i in B.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        s = s[::-1]
    elif query[0] == "2":
        if query[1] == "1":
            s = query[2] + s
        elif query[1] == "2":
            s = s + query[2]

print(s)

### FIXED CODE ###

from collections import deque
s = list(input())
q = int(input())
rev = 0
revcnt = 0
s_q = deque(s)
for _ in range(q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        revcnt += 1
        if rev == 0:
            rev = 1
        elif rev == 1:
            rev = 0

    elif query[0] == "2":
        if rev == 0:
            if query[1] == "1":
                s_q.appendleft(query[2])
            elif query[1] == "2":
                s_q.append(query[2])
        else:
            if query[1] == "1":
                s_q.append(query[2])
            elif query[1] == "2":
                s_q.appendleft(query[2])
s = list(s_q)
if revcnt%2 == 0:
    print("".join(s))
else:
    print("".join(s[::-1]))
### BUGGY CODE ###

k,n=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
#print(k,n,a)
count=1

while n < len(a):
  a=a[n-1:]
  count+=1

print(count)


### FIXED CODE ###

k,n=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
#print(k,n,a)
count=1
lena=len(a)
while n < lena:
  lena=lena-n+1
  count+=1

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

import heapq
N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))
dp = [0 for i in range(N+1)]

for i in range(2, N+1):
    kouho = []
    for k in range(1, min(i-1, K)+1):
        heapq.heappush(kouho, dp[i-k] + abs(h[i]-h[i-k]))
    dp[i] = heapq.heappop(kouho)
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))
dp = [0 for i in range(N+1)]

for i in range(2, N+1):
    kouho = []
    for k in range(1, min(i-1, K)+1):
        kouho.append(dp[i-k] + abs(h[i]-h[i-k]))
    dp[i] = min(kouho)
print(dp[N])
### BUGGY CODE ###

import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=list(map(int,read().split()))
    li=[list(map(lambda x:int(x)-1,read().split()))+[i] for i in range(Q)]
    Query=[(li[i][0],li[i][1],i) for i in range(Q)]
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = list(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1

    r = list(i+1-ai for i, ai in enumerate(a))
    r.sort()
    li = 0
    ans = 0
    for k in sorted(l.keys()):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += l[k] * (li - bisect.bisect_left(r[:li], k))
        if li >= n:
            break
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    d.reverse()
  else:
    if s[2]=="1":
      d.appendleft(s[4])
    else:
      d.append(s[4])
      
l=list(d)
print("".join(l))

### FIXED CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
flag=False

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    if flag:
      flag=False
    else:
      flag=True
  else:
    if s[2]=="1":
      if flag:
        d.append(s[4])
      else:
        d.appendleft(s[4])
    else:
      if flag:
        d.appendleft(s[4])
      else:
        d.append(s[4])
      
if flag:
  d.reverse()
  
print("".join(d))
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort()

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for s in sect:
        r, l, n = s
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sort_index = sorted(list(range(len(sect))), key=lambda i: sect[i][0])

    bit = [0] * (N + 1)

    def add(i, val):
        while i <= N:
            bit[i] += val
            i += i & -i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for i in sort_index:
        r, l, n = sect[i]
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

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


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		if 0<=i-match_cnt:
			dp_src=dp[i-match_cnt]  #dpの遷移元
			if dp_src is not None:
				if dp[i] is None:
					dp[i]=dp_src+str(a)
				else:
					if int(dp[i])<int( dp_src+str(a) ):
						dp[i]=dp_src+str(a)	
print dp[N]


### FIXED CODE ###

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]