CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = -1
Ri = len(x) - 1
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    tmp = 0
    for uk in UorD:
        cumsum += uk
        cnt_sum[cumsum + n] += 1
        tmp += sum(cnt_sum[:cumsum + n])
        if tmp >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print((x[Ri]))


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print((x[Li]))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print((x[Li]))


# Optimized solution
def f(n, a):
    x = list(sorted(set(a)))
    n_sub_half = n * (n + 1) // 2 // 2
    n_plus_minus = n * 2 + 1
    Li = 0
    Ri = len(x)
    while Ri > Li + 1:
        i = (Li + Ri) // 2
        xi = x[i]
        cnt_sum = [0] * n_plus_minus
        cumsum = 0
        cnt_sum[cumsum] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cumsum += 1
                s += cnt_sum[cumsum] + 1
            else:
                cumsum -= 1
                s -= cnt_sum[cumsum + 1] - 1
            cnt_sum[cumsum] += 1
            judge += s
            if judge >= n_sub_half:
                Li = i
                break
        else:
            Ri = i
    print((x[Li]))


n = int(eval(input()))
a = list(map(int, input().split()))
f(n, a)
# Original solution
class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = n.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

n = int(eval(input()))
m = (n * (n - 1) // 2) // 2 + 1
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(n + 10)
  ans = 0
  for x in b:
    ans += bit.bitsum(x+1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a) + 1, -1]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print((_a[t[1]]))


# Optimized solution
class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = n.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

n = int(eval(input()))
m = n * (n + 1) // 4
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a + [0]))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(max(b) + 2)
  ans = 0
  for x in b:
    ans += bit.bitsum(x + 1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a), 0]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print((_a[t[1]]))
# Original solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]


class BIT:
    # index 1~
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


M = N * (N + 1) // 2  # (N+1)C2
sorted_A = sorted(A)

inf = 0
sup = max(A) + 1
while sup - inf > 1:
    x = (sup + inf) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    min_value = min(S)
    for i in range(N + 1):
        S[i] += abs(min_value) + 1

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    if forward >= (M + 1) // 2:
        inf = x
    else:
        sup = x

for a in reversed(sorted_A):
    if inf >= a:
        print(a)
        break


# Optimized solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]

class BIT:
    # index 1~
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    return forward >= (M + 1) // 2

M = N * (N + 1) // 2  # (N+1)C2
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print((sorted_A[inf]))
# Original solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]

class BIT:
    # index 1~
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    return forward >= M // 2 # TEST　これだと通らないはず

M = N * (N + 1) // 2  # (N+1)C2
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print((sorted_A[inf]))


# Optimized solution
N = int(eval(input()))
A = [int(_) for _ in input().split()]


def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    size = max(S)
    bit = [0] * (size + 1)
    for s in S:
        i = s
        while i > 0:
            forward += bit[i]
            i -= i & -i

        i = s
        while i <= size:
            bit[i] += 1
            i += i & -i

    return forward >= (M + 1) // 2


M = N * (N + 1) // 2  # (N+1)C2
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print((sorted_A[inf]))
# Original solution
import itertools
n=int(eval(input()))
lst=list(map(int,input().split()))
ans=[]
for c in list(itertools.combinations(list(range(len(lst)+1)),2)):
    ans.append(lst[c[0]:c[1]][(c[1]-c[0])//2])
print((sorted(ans)[len(ans)//2]))


# Optimized solution
n=int(eval(input()))
lst=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
    for e in range(0,n+1-i):
        ans.append(sorted(lst[e:e+i])[i//2])
print((sorted(ans)[len(ans)//2]))
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))

A_sort=sorted(A)
ANSMIN=0
ANSMAX=N-1
cums=[None]*(N+1)

def midup(x):
    cums[0]=0
    for i in range(N):
        if A[i]>=x:
            cums[i+1]=cums[i]+1
        else:
            cums[i+1]=cums[i]-1

    MINS=min(cums)
    MAXS=max(cums)

    #print(MINS,MAXS,cums)

    bitlist=[0 for i in range(MAXS-MINS+2)]#出現個数をbit indexed treeの形でもっておく.

    NUM=0#iまでで,s_k<=s_iとなるものの個数

    for i in range(N+1):
        bitobje=cums[i]-MINS+1
        #print(i,bitobje)

        x=bitobje
        while x!=0:
            NUM+=bitlist[x]
            x-=(x&(-x))

        while bitobje<=MAXS-MINS+1:
            bitlist[bitobje]+=1

            #print(i,bitobje,bitlist)
            
            bitobje+=(bitobje &(-bitobje))

        #print(i,bitlist,NUM)

            

    #print(NUM,cums,bitlist)

    if NUM>=(N+1)*N//2/2:
        return 1
    else:
        return 0





while True:
    candi=A_sort[(ANSMIN+ANSMAX)//2]

    if midup(candi)==1:#中央値がx以上なら1を返す！
        ANSMIN=(ANSMIN+ANSMAX)//2
    else:
        ANSMAX=(ANSMIN+ANSMAX)//2

    if A_sort[ANSMIN]==A_sort[ANSMAX]:
        print((A_sort[ANSMIN]))
        break
    if ANSMIN+1==ANSMAX:
        if midup(A_sort[ANSMAX])==1:
            print((A_sort[ANSMAX]))
            break
        else:
            print((A_sort[ANSMIN]))
            break



    
    


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

A_sort=sorted(A)
ANSMIN=0
ANSMAX=N-1
cums=[None]*(N+1)

def midup(x):
    cums[0]=0
    for i in range(N):
        if A[i]>=x:
            cums[i+1]=cums[i]+1
        else:
            cums[i+1]=cums[i]-1

    MINS=min(cums)
    MAXS=max(cums)

    #print(MINS,MAXS,cums)

    bitlist=[0 for i in range(MAXS-MINS+2)]#出現個数をbit indexed treeの形でもっておく.

    NUM=0#iまでで,s_k<=s_iとなるものの個数

    for i in range(N+1):
        bitobje=cums[i]-MINS+1
        #print(i,bitobje)

        x=bitobje
        while x!=0:
            NUM+=bitlist[x]
            x-=(x&(-x))

        while bitobje<=MAXS-MINS+1:
            bitlist[bitobje]+=1
          
            bitobje+=(bitobje &(-bitobje))

    if NUM>=(N+1)*N//2/2:
        return 1
    else:
        return 0


while True:
    candi=A_sort[(ANSMIN+ANSMAX)//2]

    if midup(candi)==1:#中央値がx以上なら1を返す！
        ANSMIN=(ANSMIN+ANSMAX)//2
    else:
        ANSMAX=(ANSMIN+ANSMAX)//2

    if A_sort[ANSMIN]==A_sort[ANSMAX]:
        print((A_sort[ANSMIN]))
        break
    if ANSMIN+1==ANSMAX:
        if midup(A_sort[ANSMAX])==1:
            print((A_sort[ANSMAX]))
            break
        else:
            print((A_sort[ANSMIN]))
            break
# Original solution
def main():
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=list(map(int,open(0).read().split()))
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            i=c
            while i:
                s+=tree[i]
                i-=i&-i
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

# Optimized solution
def main():
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=list(map(int,open(0).read().split()))
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=ok+ng>>1
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            i=c
            while i:
                s+=tree[i]
                i-=i&-i
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()
# Original solution
from itertools import accumulate
N = int(eval(input()))
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2
def ok(x):
    S = list(accumulate(1 if a >= x else -1 for a in A))
    ms = min(min(S), 0)
    S = [1] + [s - ms + 1 for s in S]
    L = max(S) + 1
    B = [0] * L
    c = 0
    for s in S:
        i = s
        while i > 0:
            c += B[i]
            i -= i & -i
        i = s
        while i < L:
            B[i] += 1
            i += i & -i
    return c >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print((B[l]))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
    B = [0] * (2 * N + 1)
    res, cum, cur = 0, 0, 0
    B[0] += 1
    for a in A:
        if a >= x:
            cum += 1
            cur += B[cum]+1
        else:
            cur -= B[cum]-1
            cum -= 1
        B[cum] += 1
        res += cur
    return res >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print((B[l]))
# Original solution
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        for i in range(len(self.tree)):
            self.tree[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(eval(input()))
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

res = binsearch(0, N)
print((sorted_in[res]))


# Optimized solution
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(eval(input()))
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

res = binsearch(0, N)
print((sorted_in[res]))
# Original solution
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(eval(input()))
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

res = binsearch(0, N)
print((sorted_in[res]))


# Optimized solution
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(eval(input()))
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb // 2 else binsearch(lft, half)

res = binsearch(0, N)
print((sorted_in[res]))
# Original solution
#!/usr/bin/env python3
import sys
import itertools
import collections
from itertools import accumulate
import math
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒してない数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += b.sum(d[av])
    return ans


def solve(N: int, a: "List[int]"):

    left = 0
    right = max(a)+1
    while right - left > 1:
        mid = (right + left)//2
        # acc = [0]*N
        # for i in range(N):
        #     if a[i] >= mid:
        #         acc[i] = acc[i-1]+1
        #     else:
        #         acc[i] = acc[i-1]-1
        acc = (1 if aa >= mid else -1 for aa in a)
        acc = tuple(accumulate(acc))
        invs = inversion(acc)
        if invs < (N*(N+1)//4 + 1):
            right = mid
        else:
            left = mid
    print(left)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒していない組(l, r)の個数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += b.sum(d[av])
        b.add(d[av], 1)
    return ans


def solve(N: int, a: "List[int]"):

    def isOK(y):
        acc = (1 if aa >= y else -1 for aa in a)
        acc = tuple([0]) + tuple(accumulate(acc))
        invs = inversion(acc)
        if acc[0] == -1:
            invs -= 1
        return invs < (N*(N+1))//4

    def binary_search(x):

        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    ng, ok = binary_search(list(range(max(a))))
    print(ng)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()
# Original solution
n = int(eval(input()))
l = []
for i in range(n):
    x= list(map(int, input().split()))
    l.append(x)
def find(ele, l):
    cc = 0
    ans = []
    for i in l:
        if i==ele:
            ans.append(cc)
        cc+=1
    return ans
c = n-1
for i in l[::-1]:
    if c==n-1:
        m = max(i)
        xxx = i.copy()
        xxx.remove(m)
        m2 = max(xxx)
        if m==m2:
            count = 0
            count2 = 0
            for aa in xxx:
                if aa==m2 and count2==1:
                    ii = count
                    break
                elif aa==m2:
                    count2+=1
                count+=1
            index = [i.index(m), ii]
        else:
            index = [i.index(m), i.index(m2)]
        maxval = [m, m2]
        c-=1
        #print(index, maxval, "m")
        continue
    else:
        m = max(i)
        xxx = i.copy()
        xxx.remove(m)
        m2 = max(xxx)
        count = 0
        count2 = len(maxval)
        #print(maxval)
        found2 =find(m2,i)
        found = find(m,i)
        #print(found, found2, "Found")
        for a in maxval:
            #print(count, count2, i)
            if count==count2:
                break
            if index[count] not in found2 or len(found2)!=1:
                maxval.append(a+m2)
            if index[count] not in found or len(found)!=1:
                maxval[count]+=m
            count+=1
        if m==m2:
            index =[found[0]]*(2*count2)
        else:
            index = [found[0]]*count2+[found2[0]]*count2
        c-=1
        #print(maxval, index, "i")
print((max(maxval)))

# Optimized solution
n = int(eval(input()))
ans = [[0]*3 for xxx in range(n)]
for i in range(n):
    a,b,c = list(map(int, input().split()))
    if i==0:
        ans[0][0] = a
        ans[0][1] = b
        ans[0][2] = c 
        continue
    ans[i][0] += max(ans[i-1][1], ans[i-1][2]) + a
    ans[i][1] += max(ans[i-1][2], ans[i-1][0]) + b
    ans[i][2] += max(ans[i-1][0], ans[i-1][1]) + c
ans = ans[-1]
print((max(ans)))