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

import sys
sys.setrecursionlimit(int(1e6))

n,m=map(int,input().split())
memo=[0]*(n+1)
memo[0]=1
memo[1]=1
for i in range(m):
    memo[int(input())]=-2
def dp(i):
    if memo[i]==-2:
        return 0
    elif memo[i]==0:
        s=dp(i-1)
        if i>=2:
            s+=dp(i-2)
        memo[i]=s%(10**9+7)
        return memo[i]
    else:
        return memo[i]
        
print(dp(n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e6))

n,m=map(int,input().split())
memo=[-1]*(n+1)
memo[0]=1
memo[1]=1
for i in range(m):
    memo[int(input())]=-2
def dp(i): #i段目(0~n)まで行く方法
    if memo[i]==-2:
        return 0
    elif memo[i]==-1:
        s=dp(i-1)
        if i>=2:
            s+=dp(i-2)
        memo[i]=s%(10**9+7)
        return memo[i]
    else:
        return memo[i]
print(dp(n))
### BUGGY CODE ###

X,K,D=map(int,input().split())
key=abs(X)
if key<D:
  if K%2==0:
    print(key)
    exit()
  else:
    print(abs(key-D))
    exit()
for i in range(K):
  key-=D
  K-=1
  if key<D:
    break
if K==0:
  print(key)

else:
  Key=key-D
  if K%2==0:
    ans=abs(key)
  else:
    ans=abs(Key)
  print(ans)

### FIXED CODE ###

X,K,D=map(int,input().split())
x=abs(X)
key=x//D
Key=x%D
if key>K:
  print(x-K*D)
  exit()
KEY=Key-D
if (K-key)%2==0:
  ans=abs(Key)
else:
  ans=abs(KEY)
print(ans)
### BUGGY CODE ###

import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put((i, j))
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

n = int(input())
ls = [input() for o in range(n)]
a = [0 for j in range(len(set(ls)))]
ls.sort()
u = list(set(ls))
u.sort()
p = 0
for i in range(n):
    if i ==0:
        a[i] += 1
    else:
        if ls[i] == ls[i-1]:
            a[p] += 1
        else:
            p +=1
            a[p] +=1
t = max(a)
r = 0
for l in range(len(a)):
    if a[l] != t:
        u.remove(u[r])
    else:
        r +=1
for q in range(len(u)):
    print(u[q])


### FIXED CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]
c = collections.Counter(ls)
mx = max(c.values())
A = [e for e,j in c.items() if j == mx]
A.sort()
for p in A:
  print(p)
### BUGGY CODE ###

N,M = map(int,input().split())
XYZ = [tuple(map(int,input().split())) for _ in range(N)]
ans = 0
for b in range(8):
	dp = [0]
	for x,y,z in XYZ:
		if b&1: x *= -1
		if b&2: y *= -1
		if b&4: z *= -1
		v = x+y+z
		dp2 = dp[:]
		for i in range(len(dp)-1,-1,-1):
			if i < M:
				if i+1 >= len(dp2):
					dp2.append(dp[i] + v)
				else:
					dp2[i+1] = max(dp2[i+1], dp[i] + v)
		dp = dp2
	ans = max(ans, dp[-1])
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

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

def dp(type):
    minimize_x = type&1
    minimize_y = (type>>1)&1
    minimize_z = (type>>2)&1
    dp = [0]
    for i,(x,y,z) in enumerate(src):
        if minimize_x: x *= -1
        if minimize_y: y *= -1
        if minimize_z: z *= -1
        v = x+y+z
        dp.append(dp[-1] + v)
        for j in reversed(range(i)):
            dp[j+1] = max(dp[j+1], dp[j] + v)
    return dp[M]

ans = 0
for i in range(8):
    ans = max(ans, dp(i))
print(ans)
### BUGGY CODE ###

def solve():
    R,C,K = map(int, input().split())
    #value = [[0 for _ in range(C)] for _ in range(R)]
    dp = [[[0,0,0,0,0] for _ in range(C+1)] for _ in range (R+1)]
    for _ in range(K):
        r,c,v = map(int, input().split())
        dp[r][c][4] = v

    #print(value)
    #print(dp)

    for r in range(1, R+1):
        for c in range(1, C+1):
            v = dp[r][c][4]
            prow = max(dp[r-1][c][:4])
            if v == 0: # no item
                dp[r][c][0] = max(prow, dp[r][c-1][0])
                dp[r][c][1] = dp[r][c-1][1]
                dp[r][c][2] = dp[r][c-1][2]
                dp[r][c][3] = dp[r][c-1][3]
            else:
                dp[r][c][0] = max(prow, dp[r][c-1][0])
                dp[r][c][1] = max(dp[r][c-1][1], dp[r][c-1][0] + v, prow + v)
                dp[r][c][2] = max(dp[r][c-1][2], dp[r][c-1][1] + v)
                dp[r][c][3] = max(dp[r][c-1][3], dp[r][c-1][2] + v)

    #print(dp)
    print(max(dp[R][C][:4]))

solve()

### FIXED CODE ###

def solve():
    R,C,K = map(int, input().split())
    #value = [[0 for _ in range(C)] for _ in range(R)]
    dp = [[[0 for _ in range(C+1)] for _ in range (R+1)] for _ in range(5)]
    for _ in range(K):
        r,c,v = map(int, input().split())
        dp[4][r][c] = v

    #print(value)
    #print(dp)

    for r in range(1, R+1):
        for c in range(1, C+1):
            v = dp[4][r][c]
            prow = max(dp[0][r-1][c], dp[1][r-1][c], dp[2][r-1][c], dp[3][r-1][c])
            if v == 0: # no item
                dp[0][r][c] = max(prow, dp[0][r][c-1])
                dp[1][r][c] = dp[1][r][c-1]
                dp[2][r][c] = dp[2][r][c-1]
                dp[3][r][c] = dp[3][r][c-1]
            else:
                dp[0][r][c] = max(prow, dp[0][r][c-1])
                dp[1][r][c] = max(dp[1][r][c-1], dp[0][r][c-1] + v, prow + v)
                dp[2][r][c] = max(dp[2][r][c-1], dp[1][r][c-1] + v)
                dp[3][r][c] = max(dp[3][r][c-1], dp[2][r][c-1] + v)

    #print(dp)
    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))

solve()
### BUGGY CODE ###

from collections import deque
h, w = list(map(int, input().split()))
q = deque()
for i in range(h):
    for j, c in enumerate(input()):
        if c == "#":
            q.append((i,j, 0))
a = 0
board = [[False]*w for i in range(h)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans = 0
while q:
    i,j,cnt = q.popleft()
    if board[i][j]:
        continue
    board[i][j] = True
    ans = max(ans, cnt)
    a += 1
    if a == h*w:
        break
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w and not board[i+x][j+y]:
            q.append((i+x, j+y, cnt+1))
print(ans)


### FIXED CODE ###

from collections import deque
dx=[1,0,-1,0]
dy=[0,1,0,-1]

h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            board[i][j] = True
            q.append((i, j, 0))
        else:
            board[i][j] = False

ans = 0
while q:
    i,j,cnt = q.popleft()
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w and not board[i+x][j+y]:
            board[i+x][j+y] = True
            q.append((i+x, j+y, cnt+1))
            ans = max(ans, cnt+1)
print(ans)
### BUGGY CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(10000000)

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


@lru_cache(maxsize=None)
def rec(i, reverse):
    if i == N - 1:
        return A[i] * reverse

    num_normal = rec(i + 1, 1) + (A[i] * reverse)
    num_reverse = rec(i + 1, -1) + (-1 * A[i] * reverse)

    return max(num_normal, num_reverse)


print(rec(0, 1))


### FIXED CODE ###

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

minus_count = 0

for a in A:
    if a < 0:
        minus_count += 1

total = 0
min_num = 10 ** 9

for a in A:
    total += abs(a)
    min_num = min(min_num, abs(a))

if minus_count % 2 == 1:
    total -= 2 * min_num

print(total)
### BUGGY CODE ###

N = int(input())
l = [input() for _ in range(N)]
m = set(l)
d = dict()

for name in m:
  d[name] = l.count(name)
  

max_kv_list = sorted([kv[0] for kv in d.items() if kv[1] == max(d.values())])
for name in max_kv_list:
  print(name)

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter

def solve(l):
    d = Counter(l)
    d_max = max(d.values())
    max_d_list = sorted([k[0] for k in d.items() if k[1] == d_max])
    return max_d_list



def main():
    N = int(input())
    l = [input() for _ in range(N)]
    d = solve(l)
    for a in d:
        print(a)
    return

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

from collections import deque

class PriorityQueue:
    def __init__(self):
        self.nodes = deque([])

    def max_heapify(self, i):
        if i >= len(self.nodes): return
        left, right = (i+1)*2-1, (i+1)*2

        largest = i
        if left < len(self.nodes) and self.nodes[i] < self.nodes[left]: largest = left
        if right < len(self.nodes) and self.nodes[largest] < self.nodes[right]: largest = right

        if largest != i:
            self.nodes[i], self.nodes[largest] = self.nodes[largest], self.nodes[i]
            self.max_heapify(largest)

    def print_element(self):
        for node in self.nodes:
            print('', node, end='')
        print('')

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

pq = PriorityQueue()
pq.nodes = deque(A)

for i in range((n-1)//2, -1, -1):
    pq.max_heapify(i)

pq.print_element()


### FIXED CODE ###

n = int(input())
H = list(map(int, input().split(' ')))

def max_heapify(i):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l < n and H[l] > H[i]:
        largest = l
    else:
        largest = i
    if r < n and H[r] > H[largest]:
        largest = r

    if largest != i:
        H[i], H[largest] = H[largest], H[i]
        max_heapify(largest)

def print_elements(lst):
    for ele in lst:
        print(' {}'.format(ele), end='')
    print('')

for i in range(int(n/2), -1, -1):
    max_heapify(i)

print_elements(H)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

s = 0
w = 1000000007
for i in range(N-1):
  for j in range(i+1, N):
    s += (A[i] ^ A[j])
    s %= w
print(s%w)


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

w = 1000000007

s = 0
for k in range(60):
  n = [0, 0]
  for i in range(N):
    n[A[i]%2] += 1
    A[i] >>= 1

  s += (n[0]*n[1] << k) % w

print(s%w)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(N):
    ans+=i
print(ans)



### FIXED CODE ###

N=int(input())
ans=((N-1)*N)//2
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = [int(c) for c in S()]
    t = [0] * 2019
    r = 0
    for c in s:
        u = [0] * 2019
        u[c] = 1
        for i in range(2019):
            u[(i*10+c) % 2019] += t[i]
        t = u
        r += t[0]

    return r

print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = [int(c) for c in S()]
    t = [0] * 2019
    r = 0
    for c in s:
        u = [0] * 2019
        u[c] = 1
        for i in range(2019):
            u[(i*10+c) % 2019] += t[i]
        t = u
        r += t[0]

    return r

print(main())
### BUGGY CODE ###

import numpy as np


N, M, K = map(int, input().split())
ans = np.zeros((N+1,), dtype=int)
child = {i:[] for i in range(1, N+1)}
isBlocked = {i:[] for i in range(1, N+1)}
group = np.zeros((N+1,))

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)

for i in range(1, N+1):
    ans[i] = ans[i] - len(child[i]) - 1 
    
X = set(range(1, N+1))
g = 0
while X:
    i = X.pop()
    x = {i}
    ch = set(child[i])
    while ch:
        c = ch.pop()
        ch = (ch | set(child[c])) - set(x)
        x = x | {c}
    ans[list(x)] += len(x)
    group[list(x)] = g
    X = X - set(x)
    g += 1
        
for _ in range(K):
    c, d = map(int, input().split())
    if group[c] == group[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline

h, w = map(int, input().split())
map_arr1d = np.array([0 if s == '#' else 1 for _ in range(h) for s in input()[:-1]])
map_2d = map_arr1d.reshape(h, w)

h_map = []
for h_arr in map_2d:
    cnt = 0
    tmp_list = []
    for a in h_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    h_map.extend(tmp_list)
h_map = np.array(h_map).reshape(h, w)

w_map = []
for w_arr in map_2d.T:
    cnt = 0
    tmp_list = []
    for a in w_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    w_map.extend(tmp_list)
w_map = np.array(w_map).reshape(w, h).T
print(max((h_map + w_map).flatten())-1)


### FIXED CODE ###

import sys

input = sys.stdin.readline

h, w = map(int, input().split())
map_list = [[0 if s == '#' else 1 for s in input()[:-1]] for _ in range(h)]

h_map = []
for h_list in map_list:
    cnt = 0
    tmp_list = []
    for a in h_list:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    h_map.append(tmp_list)

w_map = []
for w_arr in [list(x) for x in zip(*map_list)]:
    cnt = 0
    tmp_list = []
    for a in w_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    w_map.append(tmp_list)
w_map = [list(x) for x in zip(*w_map)]
max_l = 0
for h_list, w_list in zip(h_map, w_map):
    for h_num, w_num in zip(h_list, w_list):
        max_l = max(max_l, h_num + w_num)
print(max_l - 1)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = 0
for i in range(N):
  move = 0
  for j in range(i,N-1):   
    if H[j] >= H[j+1]:
      move += 1
    else:
      break
  if ans <= move:
    ans = move
print(ans)
  

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans=0
cnt=0
for i in range(1,n):
  if h[i]<=h[i-1]:
    cnt+=1
    if cnt>ans:
      ans=cnt
  else:
    cnt=0
print(ans)
### BUGGY CODE ###


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

cnt = 0
for i in range(1,2*n//k+1):
    for j in range(max(1, k*i-n), min(k*i//2+1, n+1)):
        a = j
        b = k*i-a
        if a == b:
            d = 1
        else:
            d = 2
        if (b-a) % k == 0:
            cnt += ((a+n)//k - a//k)*d
print(cnt)


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
cnt = 0
if K % 2 == 0:
    for i in range(1, 2*N//K+1):
        cnt += 1 + (2*N//K-i)//2 * 6 + (2*N//K-i)//2 * ((2*N//K-i)//2 - 1) * 3
else:
    for i in range(1, N//K+1):
        cnt += 1 + (N//K-i) * 6 + (N//K-i) * ((N//K-i) - 1) * 3

print(cnt)
### BUGGY CODE ###

lst = list(map(int, input().split()))
a_lst = list(map(int, input().split()))
b_lst = list(map(int, input().split()))
c_lst = list(map(int, input().split()))

k = lst[3]
ab_lst = []
for i in a_lst:
    for j in b_lst:
        ab_lst.append(i+j)
ab_lst = sorted(ab_lst, key = lambda x: -x)[:k]
abc_lst = []
for i in ab_lst:
    for j in c_lst[:k]:
        abc_lst.append(i+j)
for i in sorted(abc_lst, key = lambda x: -x)[:k]:
    print(i)

### FIXED CODE ###

x,y,z,k = map(int, input().split())
a_lst = sorted(list(map(int, input().split())), reverse=True)
b_lst = sorted(list(map(int, input().split())), reverse=True)
c_lst = sorted(list(map(int, input().split())), reverse=True)

candidate = []
for n in range(x):
    for m in range(y):
        if (n+1)*(m+1) > k:
            break
        else:
            for l in range(z):
                if (n+1)*(m+1)*(l+1) > k:
                    break
                else:
                    candidate.append(a_lst[n]+b_lst[m]+c_lst[l])
for i in sorted(candidate, reverse=True)[:k]:
    print(i)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque([(-1,0,-2,0)])
ans=-10**18
for i,a in enumerate(A):
    while q and q[0][0]<i:
        j,n,r,x=q.popleft()
        if r<-1:
            if n==N//2-1:
                ans=max(ans,x+a)
            else:
                q.append((i,n+1,-1,x+a))
        if (j+1)//2<=n:
            q.append((i,n,r-1,x))
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque([(-1,0,-2,0)])
ans=-10**18
for i,a in enumerate(A):
    d={}
    while q and q[0][0]<i:
        j,n,r,x=q.popleft()
        if r<-1:
            if n==N//2-1:
                ans=max(ans,x+a)
            elif n not in d:
                d[n]=x
            elif d[n]<x:
                d[n]=x
        if (j+1)//2<=n:
            q.append((i,n,r-1,x))
    for n,x in d.items():
        q.append((i,n+1,-1,x+a))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)]

from collections import deque


queue = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            queue.append([i, j, 0])
            seen[i][j] = 0

def bfs(maze, seen):
    while queue:
        y, x, c = queue.popleft()
        for i, j in [1, 0], [-1, 0], [0, 1], [0, -1]:
            dy = y + i
            dx = x + j
            if dy < 0 or H <= dy or dx < 0 or W <= dx:
                continue
            if seen[dy][dx] > -1:
                continue
            if maze[dy][dx] == '#':
                continue
            seen[dy][dx] = c + 1
            queue.append([dy, dx, c+1])

def check_max(seen):
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, seen[i][j])
    return ans
    
bfs(maze, seen)
print(check_max(seen))

### FIXED CODE ###

from collections import deque



def bfs(maze, visited, queue, H, W):
    count = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + i, x + j
            if -1 < new_y < H and -1 < new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    ans = -1
    for i in range(H):
        for j in range(W):
            ans = max(ans,visited[i][j])
    return ans

H, W = map(int,input().split())

maze = [input() for i in range(H)]
visited = [[-1] * W for i in range(H)]

queue = deque([])
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            visited[i][j] = 0
            queue.append([i, j])

print(bfs(maze, visited, queue, H, W))
### BUGGY CODE ###

s = input()
og_l = len(s)
diff = 1
while diff > 0:
  cur_l = len(s)
  s = s.replace("01", '').replace("10", '')
  diff = cur_l - len(s)
print(og_l - len(s))

### FIXED CODE ###

s = input()
z = 0
o = 0
for c in s:
  if c == '0':
    z += 1
  else:
    o += 1
print(2*min(z,o))