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

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
d = Counter(A)
Q = int(input())

def sum_from_counter(d):
  return sum(map(lambda k: k * d[k], d))

for i in range(Q):
  B, C = [int(x) for x in input().split()]
  d[C] = d.get(C, 0) + d[B]
  del d[B]
  print(sum_from_counter(d))

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
d = Counter(A)
Q = int(input())

def sum_from_counter(d):
  return sum(map(lambda k: k * d[k], d))

s = sum(map(lambda k: k * d[k], d))
for i in range(Q):
  B, C = [int(x) for x in input().split()]
  d[C] = d.get(C, 0) + d[B]
  s += (C - B) * d[B]
  d[B] = 0
  print(s)
### BUGGY CODE ###

def f(i,j):
  B=[0]*n
  m=[]
  for x in range(i,n):
    a=0
    for y in range(j,n):
      a+=A[y][x]
      B[y]+=a
    m.append(max(B[j:]))
  return max(m)

n=int(raw_input())
N=range(n)
A=[map(int,raw_input().split()) for i in N]
print max([max([f(i,j) for i in N]) for j in N])

### FIXED CODE ###

def f(m,b):
  s=0
  for k in N[j:]:
    s+=A[k]
    b[k]=max(b[k],0)+s
    m=max(b[k],m)
  return m,b

m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N: m,B[j]=f(m,B[j])
print m
### BUGGY CODE ###

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

result = 0

for i in range(1, N): 
  for j in range(i+1, N+1): 
    result += A[i-1]*A[j-1]

print(result%(10**9+7))

### FIXED CODE ###

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

sum = sum(A)
result = 0

for i in range(N): 
  sum -= A[i]
  result += sum*A[i]

print(result%(10**9+7))
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = A[i]
  cnt = 0
  while(n>=1):
    bit[cnt] += n%2
    n = n//2
    cnt += 1
ans = 0
POW = 1
for j in range(60):
  ans += (bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = bin(A[i])
  for j in range(len(n)-1, 1, -1):
    bit[len(n)-j-1] += int(n[j])
ans = 0
POW = 1
for j in range(60):
  ans = (ans +bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)
### BUGGY CODE ###

k,s = map(int,input().split())
n = 0
m = k+1
for x in range(m):
    for y in range(m):
        for z in range(m):
            if z <= k and z >= 0 and x+y+z==s:
                n += 1
print(n)
                

### FIXED CODE ###

k,s = map(int,input().split())
n = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if z <= k and z >= 0 and x+y+z==s:
            n += 1
print(n)
### BUGGY CODE ###

def compute(n, k, h):
    inf = 1e9
    if n == 1:
        return 0
    dp = [inf] * n
    dp[0] = 0
    for i in range(1, n):
        cnt = 1
        while cnt <= k and i - cnt > -1:
            dp[i] = min(dp[i], dp[i - cnt] + abs(h[i] - h[i - cnt]))

    return dp[-1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    print(compute(N, K, h))


### FIXED CODE ###

n, k = [int(_) for _ in input().split()]
h = [int(_) for _ in input().split()]
inf = 1e9
dp = [inf] * n
dp[0] = 0
for i in range(1, n):
    cnt = 1
    while cnt <= k and i - cnt > -1:
        dp[i] = min(dp[i], dp[i - cnt] + abs(h[i] - h[i - cnt]))
        cnt += 1
print(dp[-1])
### BUGGY CODE ###

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df[a].add(b)
        Df[b].add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db[c].add(d)
        Db[d].add(c)

    Q = []
    ANS = []
    for i in range(1, n + 1):
        cnt = 0
        FF = set()
        C = [False]*(n + 1)
        C[i] = True
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not C[f]:
                    Q.append(f)
                    FF.add(f)
                    C[f] = True
                    cnt += 1

        ANS.append(cnt - len(Df[i]) - len(FF & Db[i] - Df[i]))

    print(*ANS)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = set()
    ANS = {}
    for i in range(1, n + 1):
        if i in C:
            continue

        C.add(i)
        Cin = set()
        Cin.add(i)
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()) - Cin:
                Q.appendleft(f)
                C.add(f)
                Cin.add(f)

        for k in Cin:
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

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

import sys

def main():
	N, K = map(int, sys.stdin.readline().rstrip().split())
	h_i = list(map(int, sys.stdin.readline().rstrip().split()))
	dp = [0] * N
	for i in range(1, N):
		dp[i] = min([abs(h_i[i] - h_i[i-j]) + dp[i-j] for j in range(1, min(i, K)+1)])
		
	return dp[-1]


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

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
if p == 1:
    print(1)
    exit()
for i in range(1,int(p**(1/n)+2)):
    if p%(i**n)==0:
        ans = i
print(ans)


### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
if n >=40:
    print(1)
    exit()
i =2
ans =1
while i**n <= p:
    if p%(i**n)==0:
        ans *= i
        p =p//(i**n)

    else:
        i += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

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

from collections import defaultdict 

N,M=map(int,input().split())

if M == 0:
  print(-1)
  exit()

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

to1d={v:{} for v in range(N)}
count=2
for p,q,c in pqc:
  if not to1d[p].get(c):
    to1d[p][c] = count
    count += 1
  if not to1d[q].get(c):
    to1d[q][c] = count
    count += 1

G = [{} for _ in range(count)]
for p,q,c in pqc:
  v1,v2 = to1d[p][c],to1d[q][c]
  G[v1][v2] = G[v2][v1] = 0
  
for v in range(N):
  if len(to1d[v])>1:
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = [INF]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in to1d[0].keys():
  v = to1d[0][c]
  G[0][v] = 1
for c in to1d[N-1].keys():
  v = to1d[N-1][c]
  G[v][1] = 0
  
d = dijkstra(0)
ans = d[1]
print(ans if ans < INF else -1)

### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

from collections import deque
import numpy as np


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = np.ones((H+2, W+2), dtype=np.int32) * -1
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

n = int(input())
a = [int(_) for _ in input().split()]
res = []
m = 0
for i in range(n//2,n):
    if a[i] == 1:
        res.append(i+1)
        m += 1
for i in range(n//2):
    k = n//2-i
    cnt = 0
    for j in res:
        if j % k == 0:
            cnt = (cnt+1)%2
    if cnt != a[k-1]:
        res.append(k)
        m += 1 
if m == 0:
    print(0)
else:
    print(m)
    for i in range(m):
        if i != 0:
            print(' ',end='')
        print(res[i],end='',)
    print()

### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
b = [0] * n
res = []
m = 0
for i in range(n//2,n):
    if a[i] == 1:
        res.append(i+1)
        b[i] = 1
        m += 1
for i in range(n//2):
    k = n//2-i
    cnt = 0
    for j in range(2*k-1,n,k):
        if b[j] == 1:
            cnt = (cnt+1)%2
    if cnt != a[k-1]:
        res.append(k)
        b[k-1] = 1
        m += 1 
if m == 0:
    print(0)
else:
    print(m)
    for i in range(m):
        if i != 0:
            print(' ',end='')
        print(res[i],end='',)
    print()
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
for l,r in LR:
    count=0
    for i in range(l-1,r-1):
        count+= S[i]+S[i+1]=="AC"
    print(count)


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[map(int,input().split()) for i in range(Q)]

data=[0 for i in range(N)]
for i in range(N-1):
    data[i+1]=data[i]
    if S[i]+S[i+1]=="AC":
        data[i+1]+=1
for l,r in LR:
    print(data[r-1]-data[l-1])
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


print(max(dp.keys()))

### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])
### BUGGY CODE ###

import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    L1 = [0]
    #print("x:", x)
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(S):
        if s == "0":
            tmp = np.array(L0) ^ A[i]
            L0.extend(list(tmp))
            L0 = set(L0)
            L0 = list(L0)
        if s == "1":
            tmp = np.array(L1) ^ A[i]
            L1.extend(list(tmp))
            L1 = set(L1)
            L1 = list(L1)

    #print(L0, L1, set(L0) <= set(L1))
    if set(L0) <= set(L1):
        print(0)
    else:
        print(1)


### FIXED CODE ###

import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    ans = 0
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(reversed(S)):
        tmp = A[N - 1 - i]
        for l0 in L0:
            if tmp ^ l0 < tmp:
                tmp = tmp ^ l0
        if tmp > 0:
            if s == "1":
                ans = 1
                break
            L0.append(tmp)
    print(ans)
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]

def bfs(x,y):
    que = deque()
    que.append((x,y))
    if S[y][x] == '.':
        dp[y][x] = 0
    else:
        dp[y][x] = 1
    while que.__len__():
        x,y = que.popleft()
        for dx,dy in ((1,0),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx >= W or sy >= H:
                continue
            if S[y][x] == '.' and S[sy][sx] == '#':
                tmp = 1
            else:
                tmp = 0
            dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
            que.append((sx,sy))
bfs(0,0)
print(dp[H-1][W-1])

### FIXED CODE ###

import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx == W or sy == H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '#':
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                if (sx,sy) not in que:
                    que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8


def main():
    n = int(input())
    polls_dict = {}
    for _ in range(n):
        poll = input()
        if poll not in polls_dict:
            polls_dict[poll] = 1
        else:
            polls_dict[poll] += 1

    max_poll = max(polls_dict.values())
    polls_set = sorted(polls_dict.keys())
    for key, value in polls_dict.items():
        if value < max_poll:
            polls_set.remove(key)

    for poll in polls_set:
        print(poll)
    
    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8


def main():
    n = int(input())
    polls_dict = {}
    for _ in range(n):
        poll = input()
        if poll not in polls_dict:
            polls_dict[poll] = 1
        else:
            polls_dict[poll] += 1

    max_poll = max(polls_dict.values())
    
    polls_set = set()
    for key, value in polls_dict.items():
        if value == max_poll:
            polls_set.add(key)

    polls_set = sorted(polls_set)
    for poll in polls_set:
        print(poll)
    
    return 0


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

n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
for i in range(n):
  price = a[i]
  nedan_list.append((i, price))
  while price > 1:
    price //= 2
    nedan_list.append((i, price))

nedan_list = sorted(nedan_list, key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a) 

for i in range(m):
  max_ = -heapq.heappop(a)
  d = max_ // 2
  heapq.heappush(a, -d)

c = 0
for i in range(len(a)):
  c -= heapq.heappop(a)
print(c)
### BUGGY CODE ###

import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        tr = self.tree
        f = self.func
        while i > 0:
            s = f(s, tr[i])
            i -= i & -i
        return s

    def put(self, i, x):
        n = self.size
        tr = self.tree
        f = self.func
        while i <= n:
            y = tr[i]
            tr[i] = f(tr[i], x)
            if y == tr[i]:
                break
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)


### FIXED CODE ###

import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        while i > 0:
            s = self.func(s, self.tree[i])
            i -= i & -i
        return s

    def put(self, i, x):
        while i <= self.size:
            self.tree[i] = self.func(self.tree[i], x)
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
minxy = 1000000000000000000
for i in range(1,n):
    s1 = sum(a[0:i])
    s2 = sum(a[i:n])
    minxy = min(minxy,abs(s1-s2))
print(minxy)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = []
for i in range(1,n):
    if i == 1:
        d.append(sum(a[0:i])-sum(a[i:n]))
    else:
        d.append(d[-1]+2*a[i-1])
for i in range(len(d)):
    d[i] = abs(d[i])
print(min(d))
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = list(input())
qs = [list(map(int, input().split())) for _ in range(Q)]
pattern = 'AC'
repatter = re.compile(pattern)
for q in qs:
    string = ''.join(S[q[0]-1:q[1]])
    result = repatter.findall(string)
    print(len(result))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = list(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt = [0]*N
is_a = False
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    cnt[i+1] = 1
for i in range(1, N):
  cnt[i] += cnt[i-1]

for l, r in lr:
  l -= 1
  r -= 1
  print(cnt[r]-cnt[l])
### BUGGY CODE ###

# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

#print("a", a)

dp = [1, 0]
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        if s+1 in a:
            dp[0] = 0 # 2回連続で穴があったら
            break
        else:
            dp.insert(0, 0) # 無を代入
        #continue
    else: # oだったら
        t = (dp[0] + dp[1]) % mod # DP!! DP!!
        dp.insert(0, t)
        
print(dp[0])


### FIXED CODE ###

# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    #print(a)
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()