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

N = input()

ans = ""

while True:
  if abs(N) % 2 == 1:
    ans += "1"
    N -= 1
  else:
    ans += "0"
  N /= -2
  if N == 1:
    ans += "1"
    break

print(ans[::-1]) 


### FIXED CODE ###

N = input()

ans = ""

while True:
  if abs(N) % 2 == 1:
    ans += "1"
    N -= 1
  else:
    ans += "0"
  N /= -2
  if N == 1:
    ans += "1"
    print(ans[::-1]) 
    break

  if N == 0:
    print (0)
    break
### BUGGY CODE ###

import numpy as np
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.zeros((N+1, W+1), np.int64)
for i, (w, v) in enumerate(wv):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j-w >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w] + v)
print(dp[N][W])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.zeros((N+1, W+1), dtype = np.int)
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(dp[N][W])
### BUGGY CODE ###

n = int(raw_input())
num_list = [int(raw_input()) for i in xrange(n)]
#print num_list

ans = max(num_list[1:]) - num_list[0]
chk = num_list[0]
# print "ans=%d, chk=%d" % (ans, chk)

for i in range(1, n - 1):
  if num_list[i] >= chk:
    continue
  max_num = max(num_list[i+1:])
  # print max_num
  tmp = max_num - num_list[i]
  if tmp > ans:
    ans = tmp
  # print "i = %d, tmp = %d, ans = %d" % (i, tmp, ans)

print ans

### FIXED CODE ###

n = int(raw_input())
num_list = [int(raw_input()) for i in xrange(n)]

minv = num_list[0]
maxv = -1000000000

for i in xrange(1, n):
  tmp = num_list[i] - minv
  maxv = tmp if tmp > maxv else maxv
  minv = num_list[i] if minv > num_list[i] else minv
  # print "i = %d, tmp = %d, maxv = %d, minv = %d" % (i, tmp, maxv, minv)

print maxv
### BUGGY CODE ###

N=int(input())
A=[]
B=[]
for i in range(N):
    _A,_B=[int(i) for i in input().split(" ")]
    A.append(_A)
    B.append(_B)

A=sorted(A)
B=sorted(B)
if N%2==1:
    print(B[(N+1)//2-1]-A[(N+1)//2-1]+1)

else:
    retval=[]
    for x1 in range(A[N//2-1],B[N//2-1]+1):
        for x2 in range(A[N//2],B[N//2]+1):
            retval.append(x1+x2)
    print(len(set(retval)))


### FIXED CODE ###

N=int(input())
A=[]
B=[]
for i in range(N):
    _A,_B=[int(i) for i in input().split(" ")]
    A.append(_A)
    B.append(_B)

A=sorted(A)
B=sorted(B)
if N%2==1:
    print(B[(N+1)//2-1]-A[(N+1)//2-1]+1)

else:
    print(B[N//2-1]-A[N//2-1]+B[N//2]-A[N//2]+1)
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(cmb(int(a+b),int(b),mod))
    

### FIXED CODE ###

p = 1000000007

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

if (X + Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if a < 0 or b < 0:
    print(0)
    exit()

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))
#他者の解答を参考にした
### BUGGY CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
Grid = [list(map(int,input().split())) for _ in range(N)]

SumCost = [[0 for _ in range(C)] for _ in range(3)]
for c in range(1,C+1):
  for i in range(N):
    for j in range(N):
      g = ((i+1)+(j+1))%3
      SumCost[g][c-1] += D[Grid[i][j]-1][c-1]

ans = 10**18
for c1 in range(1,C+1):
  for c2 in range(1,C+1):
    for c3 in range(1,C+1):
      if c1 == c2 or c2 == c3 or c3 == c1:
        continue
      ans = min(ans,SumCost[0][c1-1]+SumCost[1][c2-1]+SumCost[2][c3-1])
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
Grid = [list(map(int,input().split())) for _ in range(N)]

SumCost = [[0 for _ in range(C)] for _ in range(3)]
for c in range(1,C+1):
  for i in range(N):
    for j in range(N):
      g = ((i+1)+(j+1))%3
      SumCost[g][c-1] += D[Grid[i][j]-1][c-1]

ans = 10**18
for c1 in range(1,C+1):
  for c2 in range(1,C+1):
    for c3 in range(1,C+1):
      if c1 == c2 or c2 == c3 or c3 == c1:
        continue
      ans = min(ans,SumCost[0][c1-1]+SumCost[1][c2-1]+SumCost[2][c3-1])
print(ans)
### BUGGY CODE ###

import math

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans = math.gcd(a, b)
            ans = math.gcd(ans, c)
            sum += ans
print(sum)
            

### FIXED CODE ###


import math

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        ab = math.gcd(a, b)
        if ab == 1:
            ans += k
            continue
        for c in range(1, k+1):
            ans += math.gcd(ab,c)

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

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [0]
for i in range(1, n):
    mi = min([abs(h_list[i] - h_list[j]) + dp[j] for j in range(max(0, i - k), i)])
    dp.append(mi)
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
dp = [0]
for i in range(1, n):
    mi = min([abs(h_list[i] - h_list[j]) + dp[j] for j in range(max(0, i - k), i)])
    dp.append(mi)
print(dp[-1])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)

### FIXED CODE ###

from collections import deque
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k in range(len(visited)):
        if k > i:
            if visited[k] >= 1:
                distance[visited[k]-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)
### BUGGY CODE ###

from collections import deque

X = 998244353
N = int(input())
D = list(map(int,input().split()))
if D[0] != 0:
    ans = 0
elif N == 1:
    ans = 1
else:
    ans = 1
    Dd = deque(D)
    Dc = [Dd.count(i) for i in range(0, max(D)+1) ]

    if Dc[0]>1 or not all(Dc[1::]):
        ans = 0
    else:
        n1 = 1
        for n2 in Dc[1::]:
            nn = (n1**n2)%X
            ans *= nn
            n1 = n2
        ans%=X
print(ans)

### FIXED CODE ###

Z = 998244353
N = int(input())
D = list(map(int,input().split()))
if D[0]>0:
    ans = 0
elif N==1:
    ans = 1
else:
    D.sort()
    if D[1]==0:
        ans = 0
    else:
        D.append(-1)
        ans = 1
        cur = 0
        n1 = 1
        n2 = 1
        for d in D[1::]:
            if d == cur:
                n2 += 1
            else:
                if d == cur+1 or d == -1:
                    nn = pow(n1,n2,Z)
                    ans *= nn
                    n1 = n2
                    n2 = 1
                    cur = d
                else:
                    ans = 0
                    break
        ans%=Z
print(ans)
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
q=int(input())
for i in range(q):
    x,y=(map(int,input().split()))
    while(1):
        if x not in arr:
            break
        else:
            po=arr.index(x)
            arr[po]=y
    print(sum(arr))

### FIXED CODE ###

from collections import Counter
n=int(input())
arr=list(map(int,input().split()))
ans=Counter(arr)
sm=sum(arr)
q=int(input())
for i in range(q):
    x,y=(map(int,input().split()))
    sm=sm-(x*ans[x])
    sm=sm+(y*ans[x])
    ans[y]+=ans[x]
    ans[x]=0
    print(sm)
### BUGGY CODE ###

import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    if i%2==0:
        j=2
    else:
        j=3
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[1]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1

        if i%2==0:      
            j+=1
        else:
            j+=2
    if f==0:
        ans+=1
print(ans)



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
m=len(b)

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)
### BUGGY CODE ###

a,b = map(int,input().split( ))
ans = 0
ans2 = 0
i = 1
while a > ans:
    ans = ans + i
    i += 1
ans2 = ans + (i)
while True:
    if (ans-a) == (ans2-b):
        print(ans-a)
        break
    else:
        ans = ans-(i-1)
        ans2 = ans-i

### FIXED CODE ###

a,b = map(int,input().split( ))
c = b-a
d = 0
i = 1
ans = 0

while c > i:
    d = d+i
    i += 1
ans = d-a
print(ans)
### BUGGY CODE ###

N=int(input())
a=[i for i in range(N)]
print(sum(a))

### FIXED CODE ###

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

# -*- coding: utf-8 -*-
def main():
    N,K,Q = map(int,input().split())
    A=[int(input()) for i in range(Q)]
    Ns = []
    for _ in range(N):
        Ns.append(0)
    for i in A:
        Ns[i-1] += 1
    for j in range(N):
        if K<=sum(Ns)-Ns[j]:
            print('No')
        else:
            print('Yes')
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N,K,Q = map(int,input().split())
    A=[int(input()) for i in range(Q)]
    Ns=[0 for i in range(N)]
    for i in A:
        Ns[i-1] += 1
    SUM = sum(Ns)
    for j in range(N):
        if K<=SUM-Ns[j]:
            print('No')
        else:
            print('Yes')
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            # i<=X,Y<=j
            if i<=X and Y<=j:
                shortest[i][j] = min(j-i, X-i+1+j-Y)
            # j<=X
            elif j<=X:
                shortest[i][j] = j-i
            # i<=X<j<=Y
            elif i<=X and X<=j and j<=Y:
                shortest[i][j] = min(j-i, X-i+1+Y-j)
            # X<=i,j<=Y
            elif X<=i and j<=Y:
                shortest[i][j] = min(j-i, i-X+1+Y-j)
            # X<=i<=Y<=j
            elif X<=i and i<=Y and Y<=j:
                shortest[i][j] = min(j-i, i-X+1+j-Y)
            # Y<=i
            else:
                shortest[i][j] = j-i

    for i in range(1,N):
        count = 0
        for j in range(N):
            coll = collections.Counter(shortest[j])
            count += coll.get(i,0)
        print(count)
main()


### FIXED CODE ###

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    coll = collections.Counter()
    for i in range(N):
        k1 = abs(X-i)
        for j in range(i+1,N):
            k2 = abs(j-Y)
            shortest[i][j] = min(j-i, k1+1+k2)
        coll += collections.Counter(shortest[i])

    for i in range(1,N):
        print(coll.get(i,0))
        
main()
### BUGGY CODE ###

A, B, Q = map(int, input().split())
shrine = []
temple = []
for i in range(A):
    shrine.append(int(input()))
for i in range(B):
    temple.append(int(input()))

for i in range(Q):
    pos = int(input())
    plusA, plusB, minusA, minusB = 2E10, 2E10, -2E10, -2E10
    for i in range(A):
        a = pos - shrine[i]
        if(a>= 0):
            plusA = min(plusA, a)
        else:
            minusA = max(minusA, a)
    for i in range(B):
        b = pos - temple[i]
        if(b>= 0):
            plusB = min(plusB, b)
        else:
            minusB = max(minusB, b)
    lis = [max(plusA, plusB), abs(min(minusA, minusB)), abs(2*plusA-minusB), abs(2*minusA - plusB), abs(2*plusB - minusA), abs(2*minusB - plusA)]
    print(min(lis))

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10**18
shrine = [-INF] + [int(input()) for i in range(A)] + [INF]
temple = [-INF] + [int(input()) for i in range(B)] + [INF]

for i in range(Q):
    pos = int(input())
    b,d = bisect.bisect_right(shrine, pos), bisect.bisect_right(temple, pos)
    res = INF
    for S in [shrine[b-1], shrine[b]]:
        for T in [temple[d-1], temple[d]]:
            d1, d2 = abs(S-pos)+abs(T-S), abs(T-pos)+abs(S-T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

n=int(input())
s=input()

cnt=s.count('R')*s.count('G')*s.count('B')
for i in range(n-2):
    for j in range(i+1,n-1):
        k=2*j-i
        if j<k<n:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                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-2):
    for j in range(i+1,n-1):
        k=2*j-i
        if j<k<n:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                cnt-=1
print(cnt)
### BUGGY CODE ###

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

from collections import defaultdict, deque

S = input()
X, Y = map(int, input().split())
# [x][y][現在の移動距離][現在の向き]をメモする
memo = defaultdict(lambda :defaultdict(lambda :defaultdict(lambda :defaultdict(int))))
len_F = S.count('F')
# ゴールまでの距離と進む予定の距離の偶奇が違えば論外
if (X + Y) % 2 != len_F % 2:
    print('No')
    exit()

def bfs():
    que = deque()
    que.append([0,0,0,'r',len_F])
    while len(que) != 0:
        x, y, cur, dirc, rest = que.popleft()
        # 訪問済
        if memo[x][y][cur][dirc] == 1:
            continue
        memo[x][y][cur][dirc] = 1
        # もうゴールに届かない場合
        if rest < abs(X-x) + abs(Y-y):
            continue
        # 最後までいった時
        if cur == len(S):
            continue
        # まっすぐ
        if S[cur] == 'F':
            if dirc == 'r': x += 1
            elif dirc == 'l': x -= 1
            elif dirc == 'u': y += 1
            elif dirc == 'd': y -= 1
            que.append([x,y,cur+1,dirc,rest-1])
        # 曲がる
        elif S[cur] == 'T':
            if dirc == 'r' or dirc == 'l':
                que.append([x,y,cur+1,'u',rest])
                que.append([x,y,cur+1,'d',rest])
            elif dirc == 'u' or dirc == 'd': 
                que.append([x,y,cur+1,'r',rest])
                que.append([x,y,cur+1,'l',rest])

bfs()
if any(memo[X][Y][len(S)]):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
・さらに使い終わった1つ前はもういらないので消すことにした。
"""

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

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 1つ前は使い終わったので削除
    dpx[i-1] = set()
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
    dpy[i-1] = set()
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = set([i for i in a])
ans = 0
for i in b:
  tmp = a.count(i)
  if tmp!=i:
    if tmp<i:
      ans+=tmp
    else:
      ans+=tmp-i
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
counter = Counter(a)
ckey = list(counter.keys())
cval = list(counter.values())
ans = 0

for i in range(len(ckey)):
  if ckey[i]>cval[i]:
    ans+=cval[i]
  elif ckey[i]<cval[i]:
    ans+=cval[i]-ckey[i]
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    s = []
    for i in range(h):
        s.append(input())
    
    yoko = [[0 for i in range(w)] for j in range(h)]
    tate = [[0 for i in range(w)] for j in range(h)]

    for i in range(h):
        index = 0
        while(index < w):
            count = 0
            for j in range(index, w):
                if(s[i][j] == "#"):
                    break
                count += 1
            
            if(count == 0):
                yoko[i][index] = 0
                index += 1

            else:
                for j in range(index, index + count):
                    yoko[i][j] = count
                index += count

    for i in range(w):
        index = 0
        while(index < h):
            count = 0
            for j in range(index, h):
                if(s[j][i] == "#"):
                    break
                count += 1
            
            if(count == 0):
                tate[index][i] = 0
                index += 1

            else:
                for j in range(index, index + count):
                    tate[j][i] = count
                index += count

    result = 0

    for i in range(h):
        for j in range(w):
            result = max(result, yoko[i][j] + tate[i][j] - 1)


    print(result)


### FIXED CODE ###

if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    s = []
    for i in range(h):
        s.append(input())
    
    l = [[0 for i in range(w)] for j in range(h)]
    r = [[0 for i in range(w)] for j in range(h)]
    u = [[0 for i in range(w)] for j in range(h)]
    d = [[0 for i in range(w)] for j in range(h)]

    for i in range(h):
        for j in range(0, w):
            if(s[i][j] == "#"):
                l[i][j] = 0
            elif(j == 0):
                l[i][j] = 1
            else:
                l[i][j] = l[i][j-1] + 1
            
            tw = w-j-1
            if(s[i][tw] == "#"):
                r[i][tw] = 0
            elif(j == 0):
                r[i][tw] = 1
            else:
                r[i][tw] = r[i][tw+1] + 1
            
            if(s[i][j] == "#"):
                u[i][j] = 0
            elif(i == 0):
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1
                
            th = h-i-1
            if(s[th][j] == "#"):
                d[th][j] = 0
            elif(i == 0):
                d[th][j] = 1
            else:
                d[th][j] = d[th+1][j] + 1
            
    result = 0

    for i in range(h):
        for j in range(w):
            result = max(result, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)


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

from math import ceil
n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
l = 0
r = 10**18

def f(x):
    res = 0
    for i in range(n): res += ceil(max(0,(h[i]-b*x))/(a-b))
    return res <= x

while l+1 < r:
    m = (l+r)//2
    if f(m): r = m
    else: l = m
print(r)

### FIXED CODE ###

from math import ceil
n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
l = 0
r = max(h)

def f(x):
    res = 0
    for i in range(n): res += ceil(max(0,(h[i]-b*x))/(a-b))
    return res <= x

while l+1 < r:
    m = (l+r)//2
    if f(m): r = m
    else: l = m
print(r)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a = np.array(a)

for b, c in bc:
    a.sort()
    idx = np.where(a<c)[0].size
    idx = b if idx>b else idx
    a[0:idx] = c

print(a.sum(dtype="int64"))

### FIXED CODE ###

n, m = map(int, input().split())
*a, = map(int, input().split())
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x:-x[1])
i = 0

for b,c in bc:
    for j in range(i, min(n, i+b)):
        if a[j]<c:
            a[j] = c
    i = i+b
print(sum(a))
### BUGGY CODE ###

n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")


### FIXED CODE ###

n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")
### BUGGY CODE ###

import numpy as np

N = int(input())
L = np.sort(np.array(list(map(int, input().split(" ")))))[::-1]

cnt = 0
for i in range(0, len(L)-2):
    l1 = L[i]
    rest = L[i+1:]
    for i2 in range(0, len(rest)-1):
        l2 = rest[i2]
        if l2 < l1 / 2:
            break
        rest2 = rest[i2+1:]
        if sum(rest2 > l1 - l2) == 0:
            break
        else:
            cnt += sum(rest2 > l1 - l2)

print(cnt)

### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i):
        m = L[i]-L[j]
        k = bisect_right(L, m)
        n = max(0, j-k)
        ans+=n
print(ans)