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

n = int(input())
s = input()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
        ans += 1
print(ans)

### FIXED CODE ###

import math
n = int(input())
s = input()
r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r * g * b
for i in range(n-2):
  for j in range(i+1,math.ceil((i+n)/2)):
    if s[i] != s[j] and s[j] != s[j*2-i] and s[j*2-i] != s[i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for i in range(N):
    for j in range(N):
        if A[i] < B[j]:
            for k in range(N):
                if B[j] < C[N-1-k]:
                    ans += 1
                else:
                    break
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for i in range(N):
    a = bisect.bisect_left(A, B[i])
    c = bisect.bisect_right(C, B[i])
    ans += a*(N-c)

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

import sys
input = sys.stdin.readline
h,n=[int(item) for item in input().split()]
A=[]; dp=[pow(10,9)]*(h+10)
for i in range(n):
  x,y=map(int, input().split())
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h):
    if dp[i]==pow(10,9): continue
    index=min(h,i+a)
    dp[index]=min(dp[index],dp[i]+b)
print(dp[h])

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i] =map(int,input().split())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        for k in range(j,M+1):
          dfs(k,M,N,tmp)
    
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

### FIXED CODE ###

N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i] =map(int,input().split())

ans_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    if len(ans)==N:
      ans_list.append(ans)
    else:
      for i in range(x,M+1):
        tmp=deepcopy(ans)
        dfs(i,M,N,tmp)   
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)
### BUGGY CODE ###

n = input()
array = map(int, raw_input().split())
e_list = [array[i] for i in range(0, n, 2)]
o_list = [array[i] for i in range(1, n+1, 2)]
if e_list == o_list and len(e_list) == e_list.count(e_list[0]):
    print len(array) / 2
else:
    e_set = [n for n in set(e_list)]
    o_set = [n for n in set(o_list)]
    if len(o_set) == 1 and len(e_set) == 1:
        print 0
    else:
        e_number = []
        o_number = []
        sum = 0
        max = 0
        for number in e_set:
            sum += e_list.count(number)
            if e_list.count(number) > max:
                max = e_list.count(number)
        e_result = sum - max
        sum = 0
        max = 0
        for number in o_set:
            sum += o_list.count(number)
            if o_list.count(number) > max:
                max = o_list.count(number)
        o_result = sum - max
        print e_result + o_result


### FIXED CODE ###

# coding:utf-8
# 找第二大的数的个数
n = input()
array = map(int, raw_input().split())
e_list = [array[i] for i in range(0, n, 2)]
o_list = [array[i] for i in range(1, n+1, 2)]


def process(arr):
    arr.sort()
    num = arr[0]
    counter = 0
    amt_arr = []
    arr.append(0)
    max = 0
    max_amt_num = []
    for i in arr:
        if i == num:
            counter += 1
        else:
            if counter > max:
                max_amt_num = [num]
                max = counter
            elif counter == max:
                max_amt_num.append(num)
                max = counter
            num = i
            amt_arr.append(counter)
            counter = 1
    if len(amt_arr) == 1:
        amt_arr.append(0)
    if len(max_amt_num) > 1:
        max_amt_num = "haha"
    amt_arr.sort()

    return amt_arr[-1], amt_arr[-2], max_amt_num
v1, v2, a1 = process(e_list)
v3, v4, a2 = process(o_list)
if a1 != a2 and a1 != "haha":
    result = len(array) - v1 - v3
else:
    result = len(array) - max(v1+v4, v2+v3)
print result
### BUGGY CODE ###

import sys
from collections import defaultdict
import numpy as np


def dfs(u, dp):
    global n, ans
    if u > n:
        return
    r = required[u]
    if r == -1:
        return
    v = vvv[u]
    w = www[u]
    ndp = dp.copy()
    ndp[w:] = np.maximum(dp[w:], dp[:-w] + v)

    if u in query_ls:
        for l in query_ls[u]:
            a = ndp[l]
            for i in query_idx[u, l]:
                ans[i] = a

    dfs(u << 1, ndp)
    dfs((u << 1) + 1, ndp)


n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]
mp = iter(inp[n * 2 + 1:])
query_ls = defaultdict(list)
query_idx = defaultdict(list)
required = [-1] * (n + 1)
max_l = 0
for i, q in enumerate(zip(mp, mp)):
    u, l = q
    query_idx[q].append(i)
    query_ls[u].append(l)
    max_l = max(max_l, l)
    while u > 0:
        if required[u] >= l:
            break
        required[u] = l
        u >>= 1

ans = [0] * inp[n * 2]
dp = np.zeros(max_l + 1, np.int64)
dfs(1, dp)

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


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10**9)

N = int(input())

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

ds = set(make_divisors(N)) | set(make_divisors(N-1))

def check(n,k):
    if n<k:
        return n==1
    elif n%k==0:
        return check(n//k,k)
    else:
        return check(n-k,k)

ds.remove(1)
cnt = 0
for d in ds:
    # print(d)
    if check(N,d):
        cnt+=1
print(cnt)


### FIXED CODE ###


import sys
sys.setrecursionlimit(10**9)

N = int(input())

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

ds = set(make_divisors(N)) | set(make_divisors(N-1))

def check(n,k):
    if n<k:
        return n==1
    elif n%k==0:
        return check(n//k,k)
    else:
        return check(n%k,k)

ds.remove(1)
cnt = 0
for d in ds:
    # print(d)
    if check(N,d):
        cnt+=1
print(cnt)
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
LR = []
for _ in range(K):
  L,R = map(int,input().split())
  LR += list(range(L,R+1))
LR = np.array(LR)
MOD = 998244353
dp = np.zeros(N,"i8")
dp[0] = 1
for i in range(N):
  lr = (i+LR)
  lr = lr[lr<N]
  dp[lr] = (dp[lr]+dp[i])%MOD
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
LR = []
for _ in range(K): LR.append(list(map(int,input().split())))
MOD = 998244353
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N: dp[i+L] += dp[i]
    if i+R+1<N: dp[i+R+1] -= dp[i]
  if i>0: dp[i+1] = (dp[i+1]+dp[i])%MOD
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
  if S[i] == 'R':
    R.append(i)
  elif S[i] == 'G':
    G.append(i)
  else:
    B.append(i)

def count(X,Y,Z):
  count = 0
  for r in X:
    for g in Y:
      if (r+g)%2==0 and (r+g)//2 in Z:
        count += 1
      if 2*r-g in Z:
        count += 1
      if 2*g-r in Z:
        count += 1
  return count

if len(R)>=max(len(G),len(B)):
  print(len(R)*len(G)*len(B)-count(G,B,R))
elif len(G)>=len(R):
  print(len(R)*len(G)*len(B)-count(R,B,G))
else:
  print(len(R)*len(G)*len(B)-count(R,G,B))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = 0
G = 0
B = 0

for i in range(N):
  if S[i] == 'R':
    R += 1
  elif S[i] == 'G':
    G += 1
  else:
    B += 1
    
count = 0
for i in range(N-1):
  for j in range(i+1,N):
    if 2*j-i>=N:
      break
    if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
      count += 1

print(R*G*B-count)
### BUGGY CODE ###

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

#output
import fractions, functools

mod = 10**9 + 7

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm = lcm_list(A)

#lcm = A[0]
#for i in range(1, N):
#    lcm = lcm * A[i]//fractions.gcd(lcm, A[i])

answer = 0
for i in range(N):
    answer += lcm//A[i] % mod

print(answer % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
import fractions, functools
 
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(A)
 
answer = 0
for i in range(N):
    answer += lcm//A[i]
 
print(answer % (10**9 + 7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N=INT()

memo=[0]*50
memo[0]=memo[1]=1
def rec(n):
    if memo[n]:
        return memo[n]
    return rec(n-1)+rec(n-2)

print(rec(N))



### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N=INT()

memo=[0]*50
memo[0]=memo[1]=1
def rec(n):
    if memo[n]:
        return memo[n]
    memo[n]=rec(n-1)+rec(n-2)
    return memo[n]

print(rec(N))
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
import math
def f(x):
  return math.factorial(x)
def c(x,y):
  return f(x)//(f(x-y)*f(y))

ans=(n**2*(m-1)*m*(m+1)//6)%mod
ans=(ans+m**2*(n-1)*n*(n+1)//6)%mod
ans=(ans*c(m*n-2,k-2))%mod
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
import math
def f(x): return math.factorial(x)
def c(x,y): return f(x)//(f(x-y)*f(y))
print(((n**2*(m-1)*m*(m+1)//6+m**2*(n-1)*n*(n+1)//6)*c(m*n-2,k-2))%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools

N = int(input())
a = list(map(int, input().split()))
@functools.lru_cache(maxsize=None)
def rec(l, r):
    if r < l:
        return 0
    return max(a[l]-rec(l+1, r), a[r]-rec(l, r-1))
print(rec(0, N-1))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for i in range(N)]
for i in range(N):
    dp[i][i] = a[i]
for i in range(N-1)[::-1]:
    for j in range(i+1, N):
        dp[i][j] = max(a[i]-dp[i+1][j], a[j]-dp[i][j-1])
print(dp[0][N-1])
### BUGGY CODE ###

def solve():
    s = input()
    n = len(s)
    mod = 2019

    reminder = [0]*mod
    pre_rem = 0

    for i in range(n):
        pre_rem = (int(s[-i-1])*pow(10, i) + pre_rem) % mod
        reminder[pre_rem] += 1

    ans = reminder[0]  # そのまま割り切れる奴ら
    for rem_num in reminder[1:]:  # _nC_2をしてる
        if rem_num >= 2:
            ans += (rem_num * (rem_num -1))//2
    print(ans)
    
solve()

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-06-21 21:56:58 +0900
# LastModified: 2020-06-21 22:01:41 +0900
#


import copy

def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    for _ in range(q):
        b,c = map(int, input().split())
        new = [i if i != b else c for i in a]
        print(sum(new))
        a = copy.deepcopy(new)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-06-22 17:32:46 +0900
# LastModified: 2020-06-22 17:39:47 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*100001
    for a_ in a:
        cnt[a_] += 1

    total = sum(a)
    q = int(input())
    for _ in range(q):
        b, c = map(int, input().split())
        total += (c-b)*cnt[b]
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(total)
        




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

N,K = map(int,input().split())
P = list(map(int,input().split()))
E = [(p+1)/2 for p in P]
S = 0
for i in range(N-K+1):
  temp = sum(E[i:i+K])
  if S < temp:
    S = temp
  
print(S)


### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
E = [(p+1)/2 for p in P]
temp = sum(E[0:K])
S =  temp
for i in range(N-K):
  temp -= E[i]
  temp += E[i+K]
  if S < temp:
    S = temp  
print(S)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, Z, W = map(int, input().split())
A = [int(a) for a in input().split()]

@lru_cache(maxsize=None)
def X(i, y):
    return max([Y(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - y)])

@lru_cache(maxsize=None)
def Y(i, x):
    return min([X(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - x)])

print(X(0, W))

### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, Z, W = map(int, input().split())
A = [int(a) for a in input().split()]

@lru_cache(maxsize=None)
def X(i, y):
    return max([Y(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - y)])

@lru_cache(maxsize=None)
def Y(i, x):
    return min([X(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - x)])

print(X(0, W))
### BUGGY CODE ###

def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 300):
        fact.append(fact[-1]*i % mod)

    n, x = map(int, input().split())
    s = sorted(list(map(int, input().split())))[::-1]
    memo = [dict() for _ in [0]*(n+1)]
    memo[0][x] = fact[n]
    for i in range(n):
        inv = pow(n-i, mod-2, mod)
        for j, a in memo[i].items():
            m = a*inv % mod
            for k, l in enumerate(s[i:]):
                memo[k+i+1][j % l] = (memo[k+i+1].get(j % l, 0)+m) % mod
    ans = 0
    for i, j in memo[n].items():
        ans = (ans+i*j) % mod
    print(ans)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 300):
        fact.append(fact[-1]*i % mod)

    n, x = map(int, input().split())
    s = sorted(list(map(int, input().split())))[::-1]
    next_dict = {x: fact[n-1]}
    for i in range(n):
        memo = dict()
        inv = pow(n-i-1, mod-2, mod)
        ss = s[i]
        for j, a in next_dict.items():
            memo[j % ss] = (memo.get(j % ss, 0)+a) % mod
        for j, a in memo.items():
            next_dict[j] = (next_dict.get(j, 0)+a*inv) % mod
    ans = 0
    for i, j in memo.items():
        ans = (ans+i*j) % mod
    print(ans)


main()
### BUGGY CODE ###

import heapq

s=input()
k=int(input())
n=len(s)
ans=set()

for i in range(n+1):
    for j in range(1,n+1):
        ans.add(s[i:j])

ans.remove('')

ansh=[]
for ss in ans:
    heapq.heappush(ansh,ss)
for _ in range(k-1):
    heapq.heappop(ansh)
print(ansh[0])


### FIXED CODE ###

import heapq

s=input()
k=int(input())
n=len(s)
ans=set()

for i in range(n+1):
    j=1
    while j<=k and i+j<=n:
        ans.add(s[i:i+j])
        j+=1


ansh=[]
for ss in ans:
    heapq.heappush(ansh,ss)
for _ in range(k-1):
    heapq.heappop(ansh)
print(ansh[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input()
l = []
for i in range(Q):
    a, b = map(int, input().split())
    num = 0
    for i in range(a-1, b-1):
        if S[i] == 'A' and S[i+1] == 'C':
            num += 1
    print(num)

### FIXED CODE ###

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

pos = [0] * N
i = 0
while i < N-1:
    if S[i] == 'A':
        if S[i+1] == 'C':
            pos[i+1] = 1
    i += 1

nums = [0] * (N+1)
for i in range(1, N+1):
    nums[i] += nums[i-1] + pos[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    print(nums[r]-nums[l])
### BUGGY CODE ###

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

ans = 0
for i in range(1,2**N):
  bin_line = str(bin(i))
  bin_line = bin_line.replace('0b', '')

  count = 0
  line = []
  for j in range(len(bin_line)):
    if bin_line[j] == '1':
      count += 1
      line.append(L[N-len(bin_line)+j])
      if count > 4:
        break
  if count == 3 and len(set(line)) == 3:
    if line[0]+line[1] > line[2] and line[0]+line[2] > line[1] and line[1]+line[2]>line[0]:
      ans += 1
print(ans)
    
                 

### FIXED CODE ###

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

ans = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[i] != L[j] and L[i] != L[k] and L[j] != L[k] and L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j]+L[k] > L[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    cnt=0
    for i in range(len(a)):
        if a[i]==b:
            a[i]=c
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
T={}
for i in range(n):
    if a[i] not in T: T[a[i]]=1
    else: T[a[i]]+=1
Sum = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    if b not in T: T[b]=0
    Sum = Sum-(T[b]*b)+(T[b]*c)
    print(Sum)
    if c not in T: T[c]=T[b]
    else: T[c]+=T[b]
    T[b]=0
### BUGGY CODE ###

import math
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
#a = list(map(int,input().split()))
#b = list(map(int,input().split()))
s=int(input())
count=0
for i in range(s):
	for k in range(i,s):
		if i+k==s and i!=k:
			count+=1
print(count)

### FIXED CODE ###

import math
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
#a = list(map(int,input().split()))
#b = list(map(int,input().split()))
s=int(input())

a = math.ceil(s/2)
print(a-1)
### BUGGY CODE ###

from collections import deque
import copy

n,u,v = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
depth = [0] * n
depth2 = [0] * n
already = [1] * n
already[v-1] = 0
q = deque([v-1])
for a,b in ab:
  a,b = a-1,b-1
  tree[a].append(b)
  tree[b].append(a)
d = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    depth[now] = d
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
# print(depth)
q = deque([u-1])
d = 0
ans = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    if depth[now] == d:
      ans = max(ans,d)
      continue
    elif depth[now] < d:
      ans = max(ans,d-1)
      continue
    for i in tree[now]:
      q2.append(i)
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
print(ans)

### FIXED CODE ###

from collections import deque
import copy

n,u,v = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
depth = [0] * n
depth2 = [0] * n
already = [1] * n
already[v-1] = 0
q = deque([v-1])
for a,b in ab:
  a,b = a-1,b-1
  tree[a].append(b)
  tree[b].append(a)
d = 0
last = [0] * n
for key,i in enumerate(tree):
  if len(i) == 1:
    last[key] = 1
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    depth[now] = d
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
# print(depth)
q = deque([u-1])
d = 0
ans = 0
already = [1] * n
already[v-1] = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    if depth[now] == d:
      ans = max(ans,d)
      continue
    elif depth[now] < d:
      ans = max(ans,d-1)
      continue
    if last[now]:
      if depth[now] % 2 == d % 2:
        ans = max(ans,depth[now]-1)
      else:
        ans = max(ans,depth[now]-1)
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())
for _ in range(Q):
    newS = input()
    if int(newS[0]) == 1:
        S = S[::-1]
    else:
        if newS[2] == '1':
            S = newS[4]+S[:]
        else:
            S = S[:]+newS[4]
print(S)

### FIXED CODE ###

from collections import deque
s = input()
s = deque(s)
q = int(input())
reverse = False
for i in range(q):
    query = input()
    if len(query) == 1:
        reverse = not reverse
    else:
        if not reverse:
            if query[2] == '1':
                s.appendleft(query[4])
            else:
                s.append(query[4])
        else:
            if query[2] == '2':
                s.appendleft(query[4])
            else:
                s.append(query[4])
s ="".join(list(s))
if reverse:
    s = s[::-1]
print(s)
### BUGGY CODE ###

R,G,B,N, = list(map(int,input().split()))
s = 0
for r in range(N+1):
    for g in range(N+1):
        bp = N-r*R-g*G
        if bp>=0 and bp%B==0:
            s += 1
print(s)

### FIXED CODE ###

R,G,B,N, = list(map(int,input().split()))
s = 0
for r in range(N+1):
    for g in range(N+1):
        bp = N-r*R-g*G
        if bp>=0 and bp%B==0:
            s += 1
print(s)
### BUGGY CODE ###

import itertools

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

xor_cumsum = [0]
cumsum = [0]

for a in A:
    xor_cumsum.append(xor_cumsum[-1] ^ a)
    cumsum.append(cumsum[-1] + a)

counter = 0

for tpl in itertools.combinations(range(N+1), 2):
    if xor_cumsum[tpl[1]] ^ xor_cumsum[tpl[0]] == cumsum[tpl[1]] - cumsum[tpl[0]]:
        counter += 1

print(counter)


### FIXED CODE ###

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

r = 0
std_sum = 0 # standard summation
xor_sum = 0 # xor summation
count = 0

for l in range(N):
    while (r != N and std_sum + A[r] == xor_sum ^ A[r]):
        std_sum += A[r]
        xor_sum ^= A[r]
        r += 1
 
    count += r - l
    std_sum -= A[l]
    xor_sum ^= A[l]
 
print(count)