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

import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = []
for m in range(M):
    a = ir()
    A.append(a)
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if i in A:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = {i: False for i in range(N+1)}
for m in range(M):
    a = ir()
    A[a] = True
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if A[i]:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = input()
ans = 0
for i in range(1000):
    password = i
    #print(password)
    for j in range(n):
        if int(s[j]) == i // 100:
            for k in range(j + 1, n):
                if int(s[k]) == (i // 10) % 10:
                    for l in range(k + 1, n):
                        if int(s[l]) == i % 10:
                            ans += 1
                            break
                    
                    break
            
            break
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue
    S1 = S[S.find(num[0]) + 1:]
    if S1.find(num[1]) == -1:
        continue
    S2 = S1[S1.find(num[1]) + 1:]
    if S2.find(num[2]) == -1:
        continue
    ans += 1

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

import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    nums = []
    for _ in range(A):
        nums.append(1)
    for _ in range(B):
        nums.append(0)
    for _ in range(C):
        nums.append(-1)
    nums.sort(reverse=True)
    print(sum(nums[:K]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    A, B, C, K = map(int, input().split())
    rest = K
    ans = 0
    ans += min(A, rest)
    if K > A:
        rest -= A
        if rest > B:
            rest -= B
            ans -= min(rest, C)
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
cnt = 0
for A in range(1, N + 1):
	for B in range(1, N // A + 1):
		C = N - A * B
		if C >= 1 and A * B + C == N:
			cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
cnt = 0
for A in range(1, N + 1):
	for B in range(1, N // A + 1):
		C = N - A * B
		if C >= 1 and A * B + C == N:
			cnt += 1
print(cnt)
### BUGGY CODE ###

import sys

N,K = map(int,input().split())
sys.setrecursionlimit(2 * N)
A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]

for i in range(N):
  town[i] = [i,A[i] - 1]

def teleport(i,con):
  goal = town[i][1]
  if goal in visited or con == K:
    return goal
  else:
    visited.append(goal)
    return teleport(goal,con + 1)

l = teleport(visited[0],0)

if K <= len(visited):
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:]
  K = (K - len(visited)) % len(cycle)
  print(cycle[K] + 1)
  
##i

### FIXED CODE ###

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

A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]
flag = [-1] * N

for i in range(N):
  town[i] = [i,A[i] - 1]

f = 0

while flag[f] == -1:
  t = town[f][1]
  flag[f] = t
  f = town[t][0]
  visited.append(t)
  
l = visited[-1]
lv = len(visited)

if K <= lv:
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:-1]
  lc = len(cycle)
  print(cycle[(K - lv + 1) % lc] + 1)
##i
### BUGGY CODE ###

h, w = map(int, input().split())
A = [[] for _ in range(h)]
for i in range(h):
    A[i] = list(input())

from collections import deque

d = deque()
count_black = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            d.append((i, j))
            count_black += 1

count_while = h * w - count_black

cnt = 0
while count_while:
    while d:
        y, x = d.popleft()
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = y + dy, x + dx
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if A[ny][nx] == '#': continue
            A[ny][nx] = '#'

    # 再構築
    d = deque()
    count_black = 0
    for i in range(h):
        for j in range(w):
            if A[i][j] == '#':
                d.append((i, j))
                count_black += 1

    count_while = h * w - count_black
    cnt += 1

print(cnt)

### FIXED CODE ###

H, W = map(int, input().split())
# 壁あり
A = [['#'] * (W + 2)] +  [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W + 2)]

visited = [[True] * (W + 2) for _ in range(H + 2)]
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if A[h][w] == '.':
            visited[h][w] = False

que = []
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if visited[h][w]:
            que.append((h, w))

res = -1
while que:
    q = []
    res += 1
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        for x, y in que:
            nx, ny = x + dx, y + dy
            if not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
    que = q

print(res)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1 
        for c in L[nb+1:]:
            if c < a+b:
               ans += 1
            else:
                break
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1
        nc = bisect_left(L,a+b)
        ans += nc-nb-1
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in range(n):
    if A[i]%2:
      print(c)
      break
    A[i] //= 2
    
  c += 1

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in range(n):
    if A[i]%2:
      print(c)
      exit()
    A[i] //= 2
    
  c += 1
### BUGGY CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
ans = []
for i in range(1, n):
    l[i] *= l[i - 1]
for i in range(k - 1, n):
    if i == k - 1: ans.append(l[i])
    else:
        ans.append(l[i] // l[i - k])
for i in range(1, len(ans)):
    if ans[i] > ans[i - 1]: print('Yes')
    else: print('No')

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
for i in range(k, n):
    if l[i] > l[i - k]: print('Yes')
    else: print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K, Q = map(int, input().split())
score = []
for i in range(N):
    score.append(K)

for i in range(Q):
    answer = int(input())
    score[answer - 1] += 1
    for idx in range(N):
        score[idx] -= 1


for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

N, K, Q = map(int, input().split())
score = [0] * N

for i in range(Q):
    score[int(input()) -1 ] += +  1

for SCORE in score:
    if SCORE <= Q - K:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 80 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i*w + j][cnt]:
                tmp1 = diff[i+1][j]
                tmp2 = diff[i][j+1]

                if i+1 < h:
                    dp[(i+1)*w + j][abs(cnt - tmp1)] = True
                    if cnt + tmp1 < n:
                        dp[(i+1)*w + j][cnt + tmp1] = True

                if j+1 < w:
                    dp[i*w + j+1][abs(cnt - tmp2)] = True 
                    if cnt + tmp2 < n:
                        dp[i*w + j+1][cnt + tmp2] = True

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])

### FIXED CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

diff = [[0]*(w) for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

dp = [0] * (h*w)
dp[0] |= 1 << (13000 + diff[0][0])
dp[0] |= 1 << (13000 - diff[0][0])

for k in range(h*w):
    i = k // w
    j = k % w
    if i+1 < h:
        tmp1 = diff[i+1][j]
        dp[k + w] |= dp[k] << tmp1
        dp[k + w] |= dp[k] >> tmp1       
    if j+1 < w:
        tmp2 = diff[i][j+1]
        dp[k + 1] |= dp[k] << tmp2
        dp[k + 1] |= dp[k] >> tmp2


ans = 10**9
for i in range(81):
    if dp[w*h - 1] >> 13000 + i & 1:
        ans = min(ans, i)
for i in range(81):
    if dp[w*h - 1] >> 13000 - i & 1:
        ans = min(ans, i) 
print(ans)
### BUGGY CODE ###

import fractions  # python3.5以降ではmath


def seekGcd(A, n):
    ans = A[0]
    for i in range(1, n):
        ans = fractions.gcd(ans, A[i])  # python3.5以降ではmath.gcd
    ans_list.append(ans)


n = int(input())
A = list(tuple(map(int, input().split())))
n = len(A)
ans_list = []

for i in range(n):
    p = A.pop(0)
    seekGcd(A, n-1)
    A.append(p)

print(max(ans_list))


### FIXED CODE ###

import fractions

n = int(input())
A = list(map(int, input().split()))
n = len(A)

L = [0]
R = [0]
ans_list = []

for i in range(n-1):
    L.append(fractions.gcd(L[i], A[i]))
    R.append(fractions.gcd(R[i], A[n-1-i]))

for j in range(n):
    ans_list.append(fractions.gcd(L[j], R[-j-1]))

print(max(ans_list))
### BUGGY CODE ###

# D - Line++
import numpy as np 

N, X, Y = map(int, input().split())

T = np.zeros((N,N), dtype=np.int64)
for i in range(N):
    for j in range(i+1,N):
        T[i,j] = min(j-i, abs(i-X+1)+abs(j-Y+1)+1)

for k in range(1, N):
    print(np.count_nonzero(T==k))


### FIXED CODE ###

# D - Line++

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
cnt = [0] * N

for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X)+abs(j-Y)+1)
         cnt[tmp] += 1

for k in range(1, N):
    print(cnt[k])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i, j, 0))

    ret = 0
    visited = [False] * (W * H)
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1]:
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W]:
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

N,M = map(int,input().split())
AB = [[0,0]]*N
for n in range(N):
    temp = list(map(int,input().split()))
    if temp[0] <= M:
        AB[n] = temp
work_schedule = [0]*M
sorted_AB = sorted(AB,key=lambda x:(-x[1],x[0]))
for work in sorted_AB:
    cnt = 0
    while True:
        if work[0]-1+cnt >= M:
            break
        elif work_schedule[work[0]-1+cnt] == 0:
            work_schedule[work[0]-1+cnt]  = work[1]
            break
        elif  work_schedule[work[0]-1+cnt] != 0:
            cnt+=1
print(sum(work_schedule))

### FIXED CODE ###

from collections import defaultdict
import heapq

n, m = map(int, input().split())
dct = defaultdict(list)

for i in range(n):
    a, b = map(int, input().split())
    dct[a].append(-b)

h = []
res = 0

for i in range(1, m + 1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        res += heapq.heappop(h)

print(-res)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    for m in range(k+1):
      if i+j+m == s:
        ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= (S-x-y) <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            for s in range(0,4):
                dp[s][i+1][j+1] =  max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

if __name__ == "__main__":
    run()

### FIXED CODE ###

def run():
    # sys.stdin.readline()
    import sys
    input = sys.stdin.readline
    r,c,k = map(int,input().split())
    t = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        a,b,z = map(int,input().split())
        t[a-1][b-1] = z
    t = tuple(t)
    dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
    dp[0][0][0] = 0
    dp[1][0][0] = t[0][0]
    dp[2][0][0] = t[0][0]
    dp[3][0][0] = t[0][0]
    for i in range(r-1):
        dp[0][i+1][0] = dp[1][i][0]
        for j in range(1,4):
            dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
    for i in range(c-1):
        dp[0][0][i+1] = 0
        for j in range(1,4):
            dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
        for j in range(2,4):
            dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
        dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
    for i in range(r-1):
        for j in range(c-1):
            u = max(dp[0][i+1][j],dp[3][i][j+1])
            for s in range(0,4):
                dp[s][i+1][j+1] =  u
            u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(1,4):
                dp[s][i+1][j+1] = u
            u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
            for s in range(2,4):
                dp[s][i+1][j+1] = u
            dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
    print(dp[3][r-1][c-1])

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

X, Y = list(map(int,input().split()))

N = X

if X % Y == 0:
	print(-1)

else:
	while  N % Y != 0:
		N += X
	print(N - X)


### FIXED CODE ###

X, Y = list(map(int,input().split()))

N = X

if X % Y == 0:
	print(-1)

else:
	while  N % Y == 0:
		N += X
	print(N)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
p = [int(i) for i in input().split()]
"""
ans = 0
for i in range(n):
    tmp = 0
    for j in range(i):
        if p[j] >= p[i]:
            tmp += 1
    if tmp == i:
        ans += 1
print(ans)
"""
ans = 1
for i in range(1, n):
    tmp = []
    for j in range(i):
        tmp.append(p[j])
    tmp.sort()
    #print(tmp)
    if p[i] <= tmp[0]:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

ans = 1
tmp = p[0]
for i in range(1, n):
    if tmp >= p[i]:
        ans += 1
        tmp = p[i]
print(ans)
### BUGGY CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
if S[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(S[0])]+=1
for i in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
#print(dp)
print(dp[-1][5]%mod)


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
if S[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(S[0])]+=1
for i in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
    for m in range(13):
        dp[i][m]%=mod
#print(dp)
print(dp[-1][5]%mod)
### BUGGY CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))
b=deque()

for i in range(n):
  b.append(a[i])
  b.reverse()
print(*b)

### FIXED CODE ###

N=int(input())
A=list(input().split())
s = " ".join(A[::-2]) + " " + " ".join(A[N%2::2])
print(s)
### BUGGY CODE ###

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

broken = []
for i in range(M):
    broken.append(int(input()))

dp = [0] * (N + 2)
dp[N] = 1
for i in reversed(range(N)):
    if i in broken:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print(dp[0])


### FIXED CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)
### BUGGY CODE ###

from collections import deque
N, K, C = map(int, input().split())
S = input()

fastest = deque([])
latest = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        print(fastest[i])

### FIXED CODE ###

N, K, C = map(int, input().split())
S = input()

fastest = []
latest = []


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.append(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[- (i + 1)]:
        print(fastest[i])
### BUGGY CODE ###

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

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

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            scoreLeft=dp[i+1][j]
            score=dp[i][j]

            if (scoreLeft<score+A[i+j]*(A_index[i+j]-i)):
                dp[i+1][j]=score+A[i+j]*(A_index[i+j]-i)

            scoreRight=dp[i][j+1]

            if (scoreRight<score+A[i+j]*((N-1-j)-A_index[i+j])):
                dp[i][j+1]=score+A[i+j]*((N-1-j)-A_index[i+j])

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()


### FIXED CODE ###

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

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

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()