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

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k, 2019)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

ans = a[0]
for i in range(2020):
    ans += a[i] * (a[i]-1) // 2

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

from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[0] * (n+1) for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a][b] = 1
    ggg[b][a] = 1
    
  qq = deque()
  qq.append((1, 1))
  
  while qq:
    a, f = qq.popleft()
    if ff[a]:
      continue
    ff[a] = f
    for b in range(1, n+1):
      if ggg[a][b]:
        qq.append((b, a))
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)
 
  
  
  
if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[] for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a].append(b)
    ggg[b].append(a)
    
  qq = deque()
  qq.append(1)
  ff[1] = 1
  
  while qq:
    a = qq.popleft()
    for b in ggg[a]:
      if not ff[b]:
        ff[b] = a
        qq.append(b)
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

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

import itertools
N=int(input())
A=list(map(int,input().split()))
S=0
mod=10**9+7
for v in itertools.combinations(A,2):
    S+=v[0]^v[1]
print(S%mod)

### FIXED CODE ###

N=int(input())
bin_a="".join(["{:060b}".format(a) for a in map(int, input().split())])
mod=10**9+7
xor=0
for d in range(60):
  ones=bin_a[59-d::60].count('1')
  xor+=2**d*ones*(N-ones)    
print(xor%mod)
### BUGGY CODE ###

S = input()
K = int(input())
N = len(S)
subst = set()
for i in range(1,N+1):
    for j in range(N-i+1):
        subst.add(S[j:j+i])
L = sorted(list(subst))
print(L[K-1])


### FIXED CODE ###

S = input()
K = int(input())
N = len(S)
subst = set()
for i in range(1,K+1):
    for j in range(N-i+1):
        subst.add(S[j:j+i])
L = sorted(list(subst))
print(L[K-1])
### BUGGY CODE ###

#172D
#Sum of Divisors

N=int(input())
ans=0
for k in range(N):
    a=0
    for i in range(k+1):
        if (k+1)%(i+1)==0:
            a+=1
    ans+=(k+1)*a
print(ans)

### FIXED CODE ###

#172D
#Sum of Divisors

n=int(input())
ans=0

for i in range(1,n+1):
    j=n//i
    ans+=j*(j+1)*i/2
print(int(ans))
### BUGGY CODE ###

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

ans = float('inf')
for i in range(N):
    left = S[:i]
    right = S[i+1:]
    tmp = left.count('W') + right.count('E')
    ans = min(ans,tmp)
print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
S = input()

left = [0]*N
right = [0]*N
for i in range(1,N):
    if S[i-1]=='W':
        left[i] += left[i-1] + 1
    else:
        left[i] += left[i-1]
left = np.array(left)

for i in range(1,N):
    if S[N-i]=='E':
        right[i] += right[i-1] + 1
    else:
        right[i] += right[i-1]
right = np.array(right[::-1])

ans = (left+right).min()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    for i in range(1, len(S)):
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    if j >= kk:
                        dp[i][j] += dp[i-1][j - kk]
                    if j < kk:
                        dp[i][j] += dp[i-1][13 + j - kk]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                k = j
                if j < m:
                    k = j + 13
                dp[i][j] = dp[i-1][k-m]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

def main():
    S = input()

    tmp = [[0] * len(S)] * (10 ** 6)
    tmp[0] = [1] * len(S)

    for i in range(10**6):
        for j, s in enumerate(S):
            if s == 'R':
                tmp[i+1][j+1] += tmp[i][j]
                #print(tmp[i+1])
            if s == 'L':
                tmp[i+1][j-1] += tmp[i][j]
                #print(tmp[i+1])
        tmp[i+2] = [0] * len(S)
        if i >= 2:
            if tmp[i] == tmp[i-2]:
                if i % 2 == 0:
                    print(*tmp[i])
                    exit()
                else:
                    print(*tmp[i-1])
                    exit()
main()

### FIXED CODE ###

def runlength(S):
    d = []
    cnt = 1
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            d.append(cnt)
            cnt = 1
        else:
            cnt += 1
    else:
        d.append(cnt)
    return d


def main():
    S = input()

    d = runlength(S)
    ans = [0] * len(S)
    pre = 0
    for i in range(0,len(d),2):
        tmp = d[i] + d[i+1]
        if d[i] % 2 == 0:
            ans[pre+d[i]-1] = tmp // 2
            ans[pre+d[i]] = tmp - ans[pre+d[i]-1]
        else:
            ans[pre+d[i]] = tmp // 2
            ans[pre+d[i]-1] = tmp - ans[pre+d[i]]

        pre += tmp

    print(*ans)






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

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]

for i in range(Q):
    v = query[i]
    if v[0] == '1':
        S = S[::-1]
    else:
        if v[1] == '1':
            S = v[2] + S
        else:
            S = S + v[2]

print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
SWITCH = False

for i in range(Q):
    v = list(input().split())
    if v[0] == '1':
        SWITCH = not SWITCH

    else:
        if v[1] == '1':
            if SWITCH==False:
                S.appendleft(v[2])
            else:
                S.append(v[2])
        else:
            if SWITCH==False:
                S.append(v[2])
            else:
                S.appendleft(v[2])

S = ''.join(S)

if SWITCH:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

n = int(input())
import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

con = 0;
for k in range(1,n+1):
    c = collections.Counter(prime_factorize(k))
    x = list(c.values())
    y = len(x);
    kk = k
    for p in range(y):
        kk = kk*(x[p]+1)
    
    con += kk;
        
print(con);

### FIXED CODE ###

n = int(input())
sum = 0;

nn = n//2;
nnn = n-nn
if n <= 5000000:
    for i in range(1,n+1):
        x = n//i;
        sum += i*x*(x+1)//2;
else:
    for i in range(1,5000000+1):
        x = n//i;
        sum += i*x*(x+1)//2;
    sum += (n-5000000)*(5000001+n)//2;
print(sum);
### BUGGY CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

def coprime(a, b):
    return gcd(a, b) == 1

A , B = map(int , input().split())
gcd_value = gcd(A , B)
cd = []

for i in range(1,gcd_value + 1):
    if A % i == 0 and B % i == 0 and is_prime(i):
        cd.append(i)
print(len(cd) + 1)

### FIXED CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
A , B = map(int , input().split())
#A = 100000000000
#B = 50000000000
#print(make_divisors(A))

gcd_value = gcd(A , B)
cd = []
div = make_divisors(gcd_value)

for i in range(len(div)):
    if A % div[i] == 0 and B % div[i] == 0 and is_prime(div[i]):
        cd.append(div[i])
print(len(cd) + 1)
### BUGGY CODE ###

n, k = list(map(int, input().strip().split()))

mm = list(map(int, input().strip().split()))

dp = [float('inf')] * n

dp[0] = 0

for i in range(n):
  for j in range(1, k+1): 
    if i + j < n:
      dp[i+j] = min(dp[i+j], dp[i] + abs(mm[i+j] - mm[i]))

print(dp[n-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

DP = [0] * (N+1)

for i in range(2, N+1):
  k = max(i-K, 1)
  DP[i] = min(dp + abs(h - H[i]) for dp, h in zip(DP[k:i], H[k:i]))
print(DP[N])
### BUGGY CODE ###

import math
N,W = list(map(int, input().split(" ")))

items= [list(map(int, input().split(" "))) for _ in range(N)]


dp = [[0 for _ in range(W+1)] for _ in range(N + 1) ]
#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0




for i in range(W+1): #重さ i のときに得られる価値
    for j in range(N):  # j 個目の荷物で
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合

print(dp[N][W])

### FIXED CODE ###

import math
N,W = list(map(int, input().split(" ")))

items= [list(map(int, input().split(" "))) for _ in range(N)]


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


        w,v = items[i]
        if w_sum - w >= 0:
            dp[i + 1][w_sum]  = dp[i][w_sum - w] + v
        # print(dp[i + 1][w],dp[i][w])
        a,b = dp[i + 1][w_sum],dp[i][w_sum]
        dp[i + 1][w_sum] = max(a,b)

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

N = int(input())
A = []
for i in range(N):
    A.append(input())

List = []
for i in range(N):
    temp = {}
    for j in range(10):
        if A[i][j] in temp:
            temp[A[i][j]] += 1
        else:
            temp[A[i][j]] = 1
    List.append(temp)
    
ans = 0
i = 0
while i < len(List):
    j = i+1
    while j < len(List):
        if List[i] == List[j]:
            ans += 1
        j += 1
    i += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

L = ["0"]*N
for i in range(N):
    temp = ["0"]*10
    for j in range(10):
        temp[j] = S[i][j]
    temp.sort()
    L[i] = temp
        
L.sort()
ans = 0
cnt = 1
temp = L[0]
for i in range(1, N):
    if temp == L[i]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        temp = L[i]
        
ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    N = int(input())
    S = [int(s) for s in input().split()]
    S.sort()

    cur = []
    cur.append(S.pop(-1))

    for i in range(N):
        nxt = [j for j in cur]
        bl = len(S)
        for x in cur:
            bl = bisect.bisect_left(S,x,lo=0,hi=bl) - 1
            if bl==-1:
                return("No")
            else:
                nxt.append(S.pop(bl))
        nxt.sort(reverse=True)
        cur = [j for j in nxt]
    return("Yes")

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

### FIXED CODE ###

import sys

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])


def main():
    N = I()
    S = sorted(LI(),reverse=True)

    flag = [True]*len(S)

    cur = []
    cur.append(S[0])
    flag[0] = False

    for i in range(N):
        nxt = [x for x in cur]
        j = 0

        for k in range(len(S)):
            if j >= len(cur):
                break
            elif flag[k] and S[k]<cur[j]:
                nxt.append(S[k])
                j+=1
                flag[k] = False
        if len(cur) != j:
            return("No")
        cur = sorted(nxt,reverse=True)
    return("Yes")

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

import numpy as np

h,w,m = map(int,input().split())
t = list(list(map(int,input().split())) for _ in range(m))

b = list([0]*w for _ in range(h))

for i in range(m):
  x,y = t[i]
  b[x-1][y-1] += 1

h_max = max(np.sum(b, axis=0))
w_max = max(np.sum(b, axis=1))

h_index = [n for n, v in enumerate(np.sum(b, axis=0)) if v == h_max]
w_index = [n for n, v in enumerate(np.sum(b, axis=1)) if v == w_max]

ans = h_max + w_max

for j in h_index:
  for k in w_index:
    if b[k][j] == 0:
      print(ans)
      exit()
print(ans-1)

### FIXED CODE ###

import numpy as np

h,w,m = map(int,input().split())
t = list(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))

H = [0] * h
W = [0] * w
for x,y in t:
    H[x] += 1
    W[y] += 1
H_max = max(H)
W_max = max(W)

H_index = [x for x,i in enumerate(H) if i == H_max]
W_index = [y for y,j in enumerate(W) if j == W_max]

ans = H_max + W_max

t = set(t)
for r in H_index:
    for c in W_index:
        if (r, c) not in t:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
lis = {}
Q = int(input())
for x in A:
  if x in lis:
    lis[x] += 1
  else:
    lis[x] = 1
for i in range(Q):
  B, C = map(int, input().split())
  try:
    temp = lis[B]
    del lis[B]
    if lis == {} or not C in lis:
      lis[C] = temp
    else:
      lis[C] += temp
  except:
    pass
  ans = 0
  for x in lis:
    ans += x * lis[x]
  print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
su = sum(A)
counter = Counter(A)
lis = {}
for i in range(Q):
  B, C = map(int, input().split())
  su -= B * counter[B]
  su += C * counter[B]
  counter[C] += counter[B]
  counter[B] = 0
  print(su)
### BUGGY CODE ###

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    counts = [0] * n
    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        counts[idx] = now

    return counts


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    A = query(A)
    if full_check(A, n):
        break

print(*A)


### FIXED CODE ###

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

print(*A)
### BUGGY CODE ###

from math import floor
A,B,N=map(int,input().split())

x=N
result=[]
maxr=0
for x in reversed(range(1,N+1)):
    xb=x/B
    r=0 if xb < 1 else A*floor(xb)
    l=floor(A*xb)
    ans=l-r
    # print(xb,l,r,ans)
    result.append(ans)
    if len(result) == 1:
        maxr = ans 
    if len(result) > 1 and max(result) == maxr:
        pass

print(max(result))


### FIXED CODE ###

from math import floor
A,B,N=map(int,input().split())

x=min(B-1,N)

print(floor(A*x/B)-A*floor(x/B))
### BUGGY CODE ###

import math

def combinations_count(n, r):
    if (n != 0) & (n >= r):
        return math.factorial(n) * pow((math.factorial(n - r) * math.factorial(r)), (mod - 2))
    else:
        return 0

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0
for index, value in enumerate(a):
    ans += (combinations_count(index, k - 1) - combinations_count(n - index - 1, k - 1)) * value % mod
print(ans % mod)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0

f = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = (f[i - 1] * i) % (mod)
inv[n] = pow(f[n], mod - 2, mod)
for i in range(n - 1, 0, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

def combination(n, r):
    if (n != 0) & (n >= r):
        return f[n] * inv[r] * inv[n - r] % mod
    return 0    
    
ans = 0
for index, value in enumerate(a):
    ans += (combination(index, k - 1) - combination(n - index - 1, k - 1)) * value
print(ans % mod)
### BUGGY CODE ###

import sys

INPUT = lambda: sys.stdin.readline().rstrip()

sys.setrecursionlimit(10 ** 9)


def main():
    S = INPUT()
    N = len(S)

    s = ["", ""]
    flag = True
    for i in range(N):
        s[0] += str(i%2)
        s[1] += str((i + 1)%2)

    cnt = [0, 0]
    for i in range(N):
        for j in range(2):
            if s[j][i] != S[i]: cnt[j] += 1

    print(cnt[0] if cnt[0] < cnt[1] else cnt[1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

INPUT = lambda: sys.stdin.readline().rstrip()

sys.setrecursionlimit(10 ** 9)


def main():
    S = INPUT()
    N = len(S)

    s = ["", ""]
    for i in range(N):
        for j in range(2):
            s[j] += str((i + j)%2)

    cnt = [0, 0]
    for i in range(N):
        for j in range(2):
            if s[j][i] != S[i]: cnt[j] += 1

    print(cnt[0] if cnt[0] < cnt[1] else cnt[1])


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

import copy

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

AB = [[]] * N

for i in range(M):
    A, B = list(map(int, input().split()))
    tmp = copy.deepcopy(AB[A-1])
    tmp.append(B-1)
    AB[A-1] = tmp
    tmp = copy.deepcopy(AB[B-1])
    tmp.append(A-1)
    AB[B-1] = tmp

cnt = 0
for j in range(len(AB)):
    for val in set(AB[j]):
        if H[j] <= H[val]:
            break
    else:
        cnt += 1

print(cnt)


### FIXED CODE ###

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

result = [1] * N

for i in range(M):
    A, B = list(map(int, input().split()))
    if H[A-1] <= H[B-1]:
        result[A-1] = 0
    if H[B-1] <= H[A-1]:
        result[B-1] = 0

print(sum(result))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
# dp[x][y][Person]:= 左端がx 番目,右端がy 番目の時の,この時動かすのがPersonの時の X - Y の値(0<=x<=Y<N)
dp = [[[0, 0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i][0] = a[i]
    dp[i][i][1] = -a[i]

for i in range(1, N+1):
    # y-x = i  thus y = x+i  0<=x<N and 0<=x+i<N thus 0<=x <N-i
    for x in range(N-i):
        dp[x][x+i][0] = max(a[x]+dp[x+1][x+i][1], a[x+i]+dp[x][x+i-1][1])
        dp[x][x+i][1] = min(dp[x+1][x+i][0]-a[x], dp[x][x+i-1][0]-a[x+i])

ans = dp[0][N-1][0]
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dp = [[0]*(2*N) for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
    dp[i][i+N] = -a[i]

for i in range(1, N+1):
    for x in range(N-i):
        dp[x][x+i] = max(a[x]+dp[x+1][x+i+N], a[x+i]+dp[x][x+i-1+N])
        dp[x][x+i+N] = min(dp[x+1][x+i]-a[x], dp[x][x+i-1]-a[x+i])
ans = dp[0][N-1]
print(ans)