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

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

adj = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1    
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = my_pow(2, N - 1, MOD) - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= my_pow(2, sub, MOD) - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

adj = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1    
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

pows = [1] * N
for i in range(1, N):
    pows[i] = (pows[i - 1] * 2) % MOD

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)
### BUGGY CODE ###

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

sumpro = 0
for i in range(N):
	sumpro += sum(A[i+1:]) * A[i]

print(sumpro % 1000000007)


### FIXED CODE ###

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

s = sum(A)
sumpro = 0

for a in A[:-1]:
	s -= a
	sumpro += a * s

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

import queue
import copy

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

def movable(S,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S[px][py] == ".":
            return True
        else:
            return False
    else:
        return False

def bfs(S,sx,sy):
    S_dist = [[0 for _ in range(W)] for _ in range(H)]
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    while not q.empty():
        p = q.get()
        S[p[0]][p[1]] = "#"
        for vx,vy in vec:
            if movable(S,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                ret = S_dist[p[0]+vx][p[1]+vy]
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        S_ = copy.deepcopy(S)
        ans = max(ans,bfs(S_,i//W,i%W))
print(ans)


### FIXED CODE ###

import queue
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF = H*W+1

def movable(S,S_dist,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S_dist[px][py] == INF and S[px][py] == ".":
            return True
    return False

def bfs(S,sx,sy):
    S_dist = [[INF for _ in range(W)] for _ in range(H)]
    #Sを直接いじれば訪問済みかどうか管理できるがそれだと毎回Sをリセットする必要がある
    #S_distのみ書き込みにすればS_distはローカルだからリセットが不要
    S_dist[sx][sy] = 0
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    ret = 0
    while not q.empty():
        p = q.get()
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,S_dist,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)
### BUGGY CODE ###

R,G,B,N=map(int, input().split())

count=0
for p1 in range(N+1):
    for p2 in range(p1+1):
        rR = p2
        gG = p1-p2
        bB = N-p1
        if rR%R==0 and gG%G==0 and bB%B==0:
            count+=1
print(count)

### FIXED CODE ###

R,G,B,N=map(int, input().split())

count=0
for p1 in range(0,N+1,R):
    for p2 in range(0,N-p1+1,G):
        rR = p1
        gG = p2
        bB = N-p1-p2
        if bB%B==0:
            count+=1
print(count)
### BUGGY CODE ###

s=input()
s=s[::-1]

n=len(s)
modlist=[[0 for i in range(13)]for _ in range(n+1)]

#13で割ったあまりの判定方法
if s[0]!="?":
    modlist[0][int(s[0])]=1
elif s[0]=="?":
    for  i in range(10):
        modlist[0][i]=1
for i in range(1,n):
    if s[i]!="?":
        add=(int(s[i])*(10**(i)))%13
        for  j in range(13):
            modlist[i][j]+=modlist[i-1][(j-add)%13]
            

    else:
        for nums in range(10):
                add=nums*(10**i)%13
                for  j in range(13):
                    modlist[i][j]+=modlist[i-1][(j-add)%13]
                   

print(modlist[-2][5]%(10**9+7))                
            


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[]
for i in range(Q):
    kari=input().split()
    kouho.append(kari)
for j in range(len(kouho)):
    if kouho[j][0]=="1":
        S_list.reverse()
    else:
        if kouho[j][1]=="1":
            S_list.appendleft(kouho[j][2])
        else:
            S_list.append(kouho[j][2])
print(*S_list,sep="")

### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

n, a = map(int, input().split())
x = [int(i) for i in input().split()]
X = max(a, *x)
dp = [[[0 for k in range(n*X+1)] for j in range(n+1)]for i in range(n+1)] #full((n+1, n+1, n*X+1), 0)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j == k == s == 0: continue
            if j >= 1 and s < x[j-1]: dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j-1]: dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            else: dp[j][k][s] = 0
print(sum([dp[n][k][k*a] for k in range(1, n+1)]))

### FIXED CODE ###

n, a = map(int, input().split())
x = [int(i) for i in input().split()]
X = max(a, *x)
dp = [[[0 for k in range(n*X+1)] for j in range(n+1)]for i in range(n+1)] #full((n+1, n+1, n*X+1), 0)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j == k == s == 0: continue
            if j >= 1 and s < x[j-1]: dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j-1]: dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            else: dp[j][k][s] = 0
print(sum([dp[n][k][k*a] for k in range(1, n+1)]))
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    HW = []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "#":
                HW.append([h, w])

    res = 0
    for i in range(len(HW)):
        for j in range(i + 1, len(HW)):
            sh, sw = HW[i]
            gh, gw = HW[j]
            maze = [[f_inf] * W for _ in range(H)]
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                        continue
                    elif S[next_h][next_w] == "#":
                        continue
                    else:
                        if maze[next_h][next_w] > maze[h][w] + 1:
                            maze[next_h][next_w] = maze[h][w] + 1
                            que.append([next_h, next_w])
            if maze[gh][gw] != f_inf:
                res = max(res, maze[gh][gw])
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

from collections import deque

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

f_inf = float('inf')
ans = []
for h in range(H):
    for w in range(W):
        if grid[h][w] == "#":
            continue
        else:
            maze = [[f_inf] * W for _ in range(H)]
            sh, sw = h, w
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                        continue
                    elif grid[next_h][next_w] == "#":
                        continue
                    elif grid[next_h][next_w] == ".":
                        if maze[next_h][next_w] > maze[h][w] + 1:
                            maze[next_h][next_w] = maze[h][w] + 1
                            que.append([next_h, next_w])
                            ans.append(maze[next_h][next_w])

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

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
MAX_A=max(A)

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime=primes(MAX_A)
ans='pairwise coprime'

is_coprime=True

for p in prime:
    cnt=0
    for i,x in enumerate(A):
        if x%p==0:
            cnt+=1
    if cnt>=2:
        ans='setwise coprime'
    if cnt==N:
        is_coprime=False

if is_coprime:
    print(ans)
else:
    print('not coprime')

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from math import gcd

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

M=10**6

D=[-1]*(M+1)
D[0]=D[1]=1
for i in range(2,int(M**0.5)+1):
    if D[i]!=-1:
        continue
    for j in range(i*2,M+1,i):
        if D[j]==-1:
            D[j]=i

f=[False]*(M+1)

for x in A:
    l=[]
    while x>1:
        if f[x]==True:
            break
        if D[x]>1:
            l.append(D[x])
            x//=D[x]
        else:
            l.append(x)
            x=1
    else:
        for y in l:
            f[y]=True
        continue
    break
else:
    print('pairwise coprime')
    exit()

tmp=A[0]
for x in A[1:]:
    tmp=gcd(tmp,x)
    if tmp==1:
        print('setwise coprime')
        exit()
else:
    print('not coprime')
### BUGGY CODE ###

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

ans = 0
for i in range(N - (K - 1)):
  a = 0
  for j in range(K):
    n = p[i + j]
    a += n * (n+1)/2/n
  if a > ans:
    ans = a

print(ans)

### FIXED CODE ###

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

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

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

def main():
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  from bisect import bisect_left
  B=bisect_left
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  if not t:
    print(-1)
    exit()
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z=sorted(set(z))
  edge=[[]for _ in z]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=B(z,a),B(z,b),B(z,a+n*c),B(z,b+n*c)
    if b==n:
      l.append(y)
      d[y]=inf
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[True]*len(z)
  used[0]=False
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)
exit(0)


### FIXED CODE ###

def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)
### BUGGY CODE ###

import math
import calendar
import fractions
import itertools

n, k = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
ans = 0

while k > 0:
    h = h[:-1]
    k -= 1

ans += sum(h)

print(ans)


### FIXED CODE ###

import math
import calendar
import fractions
import itertools

n, k = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
ans = 0

if k >= n:
    print(0)
else:
    h = h[:n - k]
    print(sum(h))
### BUGGY CODE ###

N = int(input())
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
A = set(A)
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
A = set(A)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
S, T =[None] * (A+1), [None] * (B+1)
S[0], T[0] = -10**20, -10**20
for i in range(A):
    S[i+1] = int(input())
for i in range(B):
    T[i+1] = int(input())
S.append(10**20)
T.append(10**20)

def Bsearch(x, L):
    low, high = 0, len(L)
    while high-low > 1:
        mid = (low+high)//2
        if L[mid] > x:
            high = mid
        else: low = mid
    return low

def Length(x, i, L):
    return [x - L[i], L[i+1] - x]

printAns = ""

for _ in range(Q):
    x = int(input())
    sLength0, sLength1 = Length(x, Bsearch(x, S), S)
    tLength0, tLength1 = Length(x, Bsearch(x, T), T)
    Ans = min(max(sLength0, tLength0), max(sLength1, tLength1))
    Ans = min(Ans, min(sLength0 + tLength1 + min(sLength0, tLength1), sLength1 + tLength0 + min(sLength1, tLength0)))
    printAns += str(Ans) + "\n"
print(printAns)

### FIXED CODE ###

from bisect import bisect
A, B, Q = map(int, input().split())
S, T =[None] * (A+2), [None] * (B+2)
S[0], T[0] = -10**20, -10**20
for i in range(A):
    S[i+1] = int(input())
for i in range(B):
    T[i+1] = int(input())
S[A+1] = 10**20
T[B+1] = 10**20

lenS, lenT = len(S), len(T)
for _ in range(Q):
    x = int(input())
    si, ti = bisect(S, x, 0, lenS), bisect(T, x, 0, lenT)
    sLength0, sLength1 = x - S[si-1], S[si] - x
    tLength0, tLength1 = x - T[ti-1], T[ti] - x
    Ans = (max(sLength0, tLength0), max(sLength1, tLength1), sLength0 + tLength1 + min(sLength0, tLength1), sLength1 + tLength0 + min(sLength1, tLength0))
    print(min(Ans))
### BUGGY CODE ###

from collections import deque
import math
L, N = map(int, input().split())
XAntiClock, XClock = deque(), deque()
DistAntiClock, DistClock = deque(), deque()
DistAntiClock.append(0)
DistClock.append(0)
for i in range(N):
    x = int(input())
    XAntiClock.append(x)
    XClock.appendleft(L-x)
    DistAntiClock.append(DistAntiClock[-1] + 2 * x)
for i in range(N):
    DistClock.append(DistClock[-1] + XClock[i] * 2)

maxLength = max(XAntiClock[N-1], XClock[N-1])
for i in range(1, N):
    finIndex = math.ceil((i + N)/2)
    if (i + N) % 2 == 0:
        AntiClockLength = DistAntiClock[finIndex] - DistAntiClock[i-1] - XAntiClock[finIndex-1] + DistClock[N - finIndex] 
        ClockLength = DistClock[finIndex] - DistClock[i-1] - XClock[finIndex-1] + DistAntiClock[N - finIndex]
    else:
        AntiClockLength = DistAntiClock[finIndex - 1] - DistAntiClock[i-1] + DistClock[N - finIndex + 1] - XClock[N - finIndex]
        ClockLength = DistClock[finIndex - 1] - DistClock[i-1] + DistAntiClock[N - finIndex + 1] - XAntiClock[N - finIndex]
    maxLength = max(max(AntiClockLength, ClockLength), maxLength)

print(maxLength)

### FIXED CODE ###

import math
L, N = map(int, input().split())
X = [None for i in range(N)]
DistAntiClock, DistClock = [0 for i in range(N+1)], [0 for i in range(N+1)]
for i in range(N):
    X[i] = int(input())
    DistAntiClock[i+1] = DistAntiClock[i] + 2 * X[i]
for i in range(N):
    DistClock[i+1] = DistClock[i] + (L - X[-1-i]) * 2

maxLength = max(X[N-1], L - X[0])
for i in range(1, N):
    finIndex = math.ceil((i + N)/2)
    if (i + N) % 2 == 0:
        AntiClockLength = DistAntiClock[finIndex] - DistAntiClock[i-1] - X[finIndex-1] + DistClock[N - finIndex] 
        ClockLength = DistClock[finIndex] - DistClock[i-1] - (L-X[-finIndex]) + DistAntiClock[N - finIndex]
    else:
        AntiClockLength = DistAntiClock[finIndex - 1] - DistAntiClock[i-1] + DistClock[N - finIndex + 1] - (L - X[finIndex - 1])
        ClockLength = DistClock[finIndex - 1] - DistClock[i-1] + DistAntiClock[N - finIndex + 1] - X[N - finIndex]
    maxLength = max(max(AntiClockLength, ClockLength), maxLength)

print(maxLength)
### BUGGY CODE ###

import math
ans=0

K=int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      if i==1 or j==1 or k==1:
        ans+=1
      else:
        ans+=math.gcd(i,(math.gcd(j,k)))
print(ans)

### FIXED CODE ###

import math
ans=0

K=int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    num=math.gcd(i,j)
    for k in range(1,K+1):
      if num==1:
        ans+=1
      else:
        ans+=math.gcd(num,k)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = [0]*n
for i in range(n):
    cnt[i] = s[0:i].count("W") + s[i+1:n].count("E")
print(min(cnt))

### FIXED CODE ###

n = int(input())
s = input()
cnt = [0]*n
cnt_e = [0]*n
cnt_w = [0]*n
e = 0
w = 0
for i in range(n):
    if s[i] == "E":
        e += 1
    else :
        w += 1
    cnt_e[i] = e
    cnt_w[i] = w

cnt[0] =  e - cnt_e[0]
for i in range(1,n):
    cnt[i] = cnt_w[i-1] + e - cnt_e[i]

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

# coding: utf-8 
r, g, b, n = map(int, input().split())
cnt = 0
for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if n-i*r-j*g>=0 and (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)


### FIXED CODE ###

# coding: utf-8 
r, g, b, n = map(int, input().split())
cnt = 0
for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and len({s[i], s[j], s[k]}) == 3:
            cnt -= 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and len({s[i], s[j], s[k]}) == 3:
            cnt -= 1
print(cnt)