Problem:
 Score : 500 points    Problem Statement Let N be a positive integer.  There is a numerical sequence of length 3N , a = (a_1, a_2, ..., a_{3N}) .
Snuke is constructing a new sequence of length 2N , a' , by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: ( the sum of the elements in the first half of a') - ( the sum of the elements in the second half of a') .  Find the maximum possible score of a' .      Constraints  1 ≤ N ≤ 10^5  a_i is an integer.  1 ≤ a_i ≤ 10^9       Partial Score  In the test set worth 300 points, N ≤ 1000 .         Input Input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_{3N}       Output Print the maximum possible score of a' .        Sample Input 1 2
3 1 4 1 5 9      Sample Output 1 1  When a_2 and a_6 are removed, a' will be (3, 4, 1, 5) , which has a score of (3 + 4) - (1 + 5) = 1 .       Sample Input 2 1
1 2 3      Sample Output 2 -1  For example, when a_1 are removed, a' will be (2, 3) , which has a score of 2 - 3 = -1 .       Sample Input 3 3
8 2 2 7 4 6 5 3 8      Sample Output 3 5  For example, when a_2 , a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3) , which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5 .

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
left=[0]*(2*n+1)
right=[0]*(2*n+1)
now_a=a[:n]
left[n]=sum(now_a)
now_a.sort()
from heapq import heapify,heappop,heappush
heapify(now_a)
for i in range(n,2*n):
  if a[i]>now_a[0]:
    left[i+1]=left[i]+a[i]-now_a[0]
    heappop(now_a)
    heappush(now_a,a[i])
  else:
    left[i+1]=left[i]
b=[-x for x in a]
now_b=b[-n:]
right[n]=sum(now_b)
now_b.sort()
heapify(now_b)
for i in range(n,2*n):
  if b[-i-1]>now_b[0]:
    right[i+1]=right[i]+b[-i-1]-now_b[0]
    heappop(now_b)
    heappush(now_b,b[-i-1])
  else:
    right[i+1]=right[i]
ans=-pow(10,14)
for i in range(n+1):
  ans=max(ans,left[n+i]+right[2*n-i])
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    first = a[:n]
    second = a[n:2 * n]
    third = a[2 * n:3 * n]

    first_max = [0] * (n + 1)
    third_min = [0] * (n + 1)

    first_max[0] = sum(first)
    third_min[0] = sum(third)

    pq_first = PriorityQueue(first)
    cur = first_max[0]
    for i, x in enumerate(second, 1):
        if pq_first.top() < x:
            cur -= pq_first.pop()
            cur += x
            pq_first.push(x)
        first_max[i] = cur

    pq_third = PriorityQueue(third, desc=True)
    cur = third_min[0]
    for i, x in enumerate(second[::-1], 1):
        if pq_third.top() > x:
            cur -= pq_third.pop()
            cur += x
            pq_third.push(x)
        third_min[i] = cur

    ans = -INF
    for i in range(n + 1):
        fi_idx = i
        th_idx = n - i
        ans = max(ans, first_max[fi_idx] - third_min[th_idx])

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq


def solve(n):
  a = list(map(int,input().split()))
  
  
  leftHsum = [0 for i in range(n+1)]
  leftH = a[0:n]
  heapq.heapify(leftH)
  leftHsum[0] = sum(leftH) 
  for i in range(n):
    if leftH[0] < a[n+i]:
      leftHsum[i+1] = leftHsum[i] - leftH[0] + a[n+i]
      heapq.heappop(leftH)
      heapq.heappush(leftH, a[n+i])
    else:
      leftHsum[i+1] = leftHsum[i]
  
  
  rightHsum = [0 for i in range(n+1)]
  rightH = list(map(lambda x: -x,a[2*n:3*n]))
  heapq.heapify(rightH)
  rightHsum[0] = - sum(rightH)
  for i in range(n):
    if rightH[0] < -a[2*n-i-1]:
      rightHsum[i+1] = rightHsum[i] + rightH[0] + a[2*n-i-1]
      heapq.heappop(rightH)
      heapq.heappush(rightH, -a[2*n-i-1])
    else:
      rightHsum[i+1] = rightHsum[i]
  result = -1000000000000000000
  
  
  for i in range(n+1):
    result = max(result, leftHsum[0+i]-rightHsum[n-i])
  return result





n = int(input())
print(solve(n))

Solution (Python):
import heapq

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

R=sorted(A[:N])
SUM1=[sum(A[:N])]
for i in range(N,2*N):
    heapq.heappush(R,A[i])
    tmp=heapq.heappop(R)
    SUM1.append(SUM1[-1]+A[i]-tmp)

B=list(map(lambda x:x*(-1),A[2*N:3*N]))
B.sort()
SUM2=[-sum(B)]
for i in range(2*N-1,N-1,-1):
    heapq.heappush(B,-A[i])
    tmp=heapq.heappop(B)
    SUM2.append(SUM2[-1]+A[i]+tmp)

ans=-float("inf")
for i in range(N+1):
    ans=max(ans,SUM1[i]-SUM2[-(i+1)])
print(ans)

Solution (Python):
import heapq
n = int(input())
a = list(map(int, input().split()))

l_sum = [0 for _ in range(n+1)]
r_sum = [0 for _ in range(n+1)]

que = a[:n]
l_sum[0] = sum(que)
heapq.heapify(que)

for i in range(n):
    l_sum[i+1] = l_sum[i]

    if que[0] < a[n+i]:
        l_sum[i+1] += a[n+i] - que[0]
        heapq.heappop(que)
        heapq.heappush(que, a[n+i])


que = [-a[i] for i in range(2*n, 3*n)]
r_sum[0] = -sum(que)
heapq.heapify(que)

for i in range(n):
    r_sum[i+1] = r_sum[i]
    
    if -que[0] > a[2*n-1-i]:
        r_sum[i+1] += a[2*n-1-i] + que[0]
        heapq.heappop(que)
        heapq.heappush(que, -a[2*n-1-i])


ans = -1e15
for x in range(n+1):
    ans = max(ans, l_sum[x] - r_sum[n-x])

print(ans)

Solution (Python):

import heapq
N = int(input())
a = list(map(int, input().split()))
S = sum(a[:N])
b = a[:N]
heapq.heapify(b)
dpmax = [S for i in range(N+1)]

for i in range(N, 2*N):
    heapq.heappush(b, a[i])
    d = heapq.heappop(b)
    S += a[i]-d
    dpmax[i-N+1] = S

c = a[-N:]
for i in range(N):
    c[i] = -c[i]
T = sum(c)
heapq.heapify(c)
dpmin = [-T for i in range(N+1)]


for i in range(N, 2*N):
    heapq.heappush(c, -a[-1-i])
    d = heapq.heappop(c)
    T += -a[-1-i]-d
    dpmin[i+1-N] = -T

ans = -1000000000000000000000000000000
for i in range(N+1):
    ans = max(ans, dpmax[i]-dpmin[N-i])
print(ans)

Solution (Python):


import sys

















from heapq import heapify, heappush, heappop 







from operator import itemgetter              




def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    
    left = sum(L[:n])
    l_h = L[:n]    
    heapify(l_h)

    right = 0
    tmp = [[i, L[i]] for i in range(n, 3*n)]
    assert (len(tmp) == 2*n)
    tmp.sort(key=itemgetter(1))
    latter_min_nth = [False] * 3 * n    
    sub_member_r_h = []    
    for ind in range(n):
        i, num = tmp[ind]
        right += num
        latter_min_nth[i] = True
    for ind in range(n, 2*n):
        i, num = tmp[ind]
        sub_member_r_h.append([num, i])
    heapify(sub_member_r_h)        
    

    max_score = left - right
    
    for i in range(n, 2*n):
        
        if l_h[0] < L[i]:
            
            left -= heappop(l_h)
            left += L[i]
            heappush(l_h, L[i])
        if latter_min_nth[i]:
            
            latter_min_nth[i] = False
            right -= L[i]
            while sub_member_r_h[0][1] <= i:
                heappop(sub_member_r_h)    
            num, ind = heappop(sub_member_r_h)
            assert (ind > i)
            right += num
            latter_min_nth[ind] = True
        
        max_score = max(max_score, left - right)
    
    print(max_score)


if __name__ == "__main__":
    main()



"""
15 
25 sub
"""

Solution (Python):
from heapq import heapify, heappop, heappush

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

L = [[a, i] for i, a in enumerate(A[:2*N])]
Sl = 0
heapify(L)
used = set()
for i in range(N):
  a, i = heappop(L)
  used.add(i)
  Sl -= a

R = A[2*N:].copy()
Sr = -sum(R)
heapify(R)

ans = Sl - Sr
for i in range(2*N-1, N-1, -1):
  a = - A[i]
  r =  - heappop(R)
  if a > r:
    heappush(R, -r)
  else:
    Sr += a - r
    heappush(R, -a)
  if i in used:
    while L:
      l, j = heappop(L)
      l *= -1
      if j < i:
        Sl += l - a
        used.add(j)
        break
  ans = max(ans, Sl - Sr)

print(ans)

Solution (Python):

import sys
from heapq import heappush,heappop,heapify
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

def main():
    N=int(input())
    a=list(map(int,input().split()))
    f=[0]*(N+1)
    s=[0]*(N+1)
    h=a[:N]
    heapify(h)
    f[0]=sum(a[:N])
    for i in range(N):
        heappush(h,a[N+i])
        f[i+1]=f[i]+a[N+i]-heappop(h)
    h=[-x for x in a[2*N:]]
    heapify(h)
    s[N]=sum(a[2*N:])
    for i in range(N):
        heappush(h,-a[2*N-i-1])
        s[N-i-1]=s[N-i]+a[2*N-i-1]+heappop(h)
    ans=-INF
    for x,y in zip(f,s):
        ans=max(ans,x-y)
    print(ans)
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
la = [[0]*2 for i in range(n+1)]
for i in range(n):
    sa += A[i]
    heapq.heappush(hf,A[i])
for i in range(2*n,3*n):
    sb += A[i]
    heapq.heappush(hb,-A[i])
la[0][0] = sa
la[-1][-1] = sb
for i in range(n,2*n):
    now = A[i]
    now2 = A[-1-i]
    heapq.heappush(hf,now)
    heapq.heappush(hb,-now2)
    h1 = heapq.heappop(hf)
    h2 = -heapq.heappop(hb)
    sa += now-h1
    sb += now2 -h2
    la[i-n+1][0] = sa
    la[-i+n-2][1] = sb

ans = -float("INF")
for i,j in la:
    ans = max(ans,i-j)
print(ans)

Solution (Python):
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
la = [[0]*2 for i in range(n+1)]
for i in range(n):
    sa += A[i]
    heapq.heappush(hf,A[i])
for i in range(2*n,3*n):
    sb += A[i]
    heapq.heappush(hb,-A[i])
la[0][0] = sa
la[-1][-1] = sb
for i in range(n,2*n):
    now = A[i]
    now2 = A[-1-i]
    heapq.heappush(hf,now)
    heapq.heappush(hb,-now2)
    h1 = heapq.heappop(hf)
    h2 = -heapq.heappop(hb)
    sa += now-h1
    sb += now2 -h2
    la[i-n+1][0] = sa
    la[-i+n-2][1] = sb

ans = -float("INF")
for i,j in la:
    ans = max(ans,i-j)
print(ans)

Solution (Python):
import heapq

n = int(input().strip())
a = list(map(int, input().split()))
pre = a[:n]
heapq.heapify(pre)
suf = list(map(lambda x: -x, a[(2 * n):]))
heapq.heapify(suf)
left = {}
right = {}
pre_sum = sum(pre)
suf_sum = -sum(suf)
left[n - 1] = pre_sum
right[2 * n] = suf_sum
for i in range(n, 2 * n):
    heapq.heappush(pre, a[i])
    pre_sum = pre_sum + a[i] - heapq.heappop(pre)
    left[i] = pre_sum
for i in range(2 * n - 1, n - 1, -1):
    heapq.heappush(suf, -a[i])
    suf_sum = suf_sum + a[i] + heapq.heappop(suf)
    right[i] = suf_sum
ans = -float('inf')
for i in range(n - 1, 2 * n):
    ans = max(ans, left[i] - right[i + 1])
print(ans)

Solution (Python):
import heapq
n= int(input())
a=list(map(int,input().split()))
pres = a[:n]
heapq.heapify(pres)
apresum = [0]*(n+1)
aps = sum(pres)
apresum[0]=aps
posts = list(map(lambda x: -1 * x, a[::-1][:n]))
heapq.heapify(posts)
apossum = [0]*(n+1)
aqs = sum(posts)
apossum[0]=aqs
for i in range(1,n+1):
    tempprea = a[n+i-1]
    tempposta = -1 * a[2*n-i]
    heapq.heappush(pres,tempprea)
    tempprepop=heapq.heappop(pres)
    aps += tempprea-tempprepop
    apresum[i]=aps
    heapq.heappush(posts,tempposta)
    temppostpop=heapq.heappop(posts)
    aqs += tempposta - temppostpop
    apossum[i]=aqs
print(max([x+y for x,y in zip(apresum,apossum[::-1])]))

Solution (Python):
import heapq
N=int(input())
alist=list(map(int,input().split()))

sum1=0
hq1=[]
for i in range(N):
  sum1+=alist[i]
  heapq.heappush(hq1,alist[i])
sum1_list=[sum1]
for i in range(N,2*N):
  heapq.heappush(hq1,alist[i])
  min_s1=heapq.heappop(hq1)  
  sum1+=alist[i]-min_s1
  sum1_list.append(sum1)

  
alist_rev=alist[::-1]  
sum2=0
hq2=[]
for i in range(N):
  sum2+=alist_rev[i]
  heapq.heappush(hq2,-alist_rev[i])
sum2_list=[sum2]
for i in range(N,2*N):
  heapq.heappush(hq2,-alist_rev[i])
  max_s2=-heapq.heappop(hq2)
  sum2+=alist_rev[i]-max_s2
  sum2_list.append(sum2)
sum2_list.reverse()


answer=-float("inf")
for i in range(N+1):
  answer=max(answer,sum1_list[i]-sum2_list[i])

print(answer)

Solution (Python):
import heapq

def score(init, cand):
    
    score = [0] * (n+1)
    score[0] = sum(init)
    hp = init
    heapq.heapify(hp)
    
    for i,ai in enumerate(cand):
    
        if hp[0] < ai:
            min_a = heapq.heappop(hp)
            score[i+1] = score[i] + (ai - min_a)
            heapq.heappush(hp, ai)
        else:
            score[i+1] = score[i]
    
    return score
    
n = int(input())
a = list(map(int,input().split()))
minus_a = [-x for x in a[::-1]]

former_score = score(a[:n],a[n:2*n])
latter_score = score(minus_a[:n],minus_a[n:2*n])[::-1]

ans = max(x+y for x,y in zip(former_score,latter_score))

print(ans)

Solution (Python):
from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
tmp = list(map(int, input().split(' ')))
former_A = deque(tmp)
latter_A = deque(tmp.copy())
former_heap = list()
latter_heap = list()
for _ in range(N):
    former_heap.append(former_A.popleft())
    latter_heap.append(- latter_A.pop())
heapify(former_heap)
heapify(latter_heap)

former_sum = sum(former_heap)
former_sum_list = [former_sum]
for k in range(N):
    new_a = former_A.popleft()
    heappush(former_heap, new_a)
    min_a = heappop(former_heap)
    former_sum += new_a - min_a
    former_sum_list.append(former_sum)

latter_sum = sum(latter_heap)
latter_sum_list = [latter_sum]
for k in range(N):
    new_a = - latter_A.pop()
    heappush(latter_heap, new_a)
    min_a = heappop(latter_heap)
    latter_sum += new_a - min_a
    latter_sum_list.append(latter_sum)
latter_sum_list.reverse()

answer = max([former + latter for former, latter in zip(former_sum_list, latter_sum_list)])
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

n, *a = map(int, read().split())
a_rev = list(map(lambda x: int(x) * (-1), a[::-1]))


def get_sum_list(a):
    h = []
    res = []
    cnt = 0
    for i, aa in enumerate(a[:2 * n]):
        heappush(h, aa)
        cnt += aa
        if i >= n:
            cnt -= heappop(h)
        if i >= n - 1:
            res.append(cnt)
    return res


left = get_sum_list(a)
right = get_sum_list(a_rev)
ans = -float('inf')
for i in range(n + 1):
    memo = left[i] + right[n - i]
    if ans < memo:
        ans = memo
print(ans)

Solution (Python):
import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AH = sorted([(a, i) for i, a in enumerate(A[:2 * N])], reverse=True)
    AT = sorted(A[-N:])
    ATT = []
    for a in AT:
        heapq.heappush(ATT, -a)
    used = [False] * (2 * N)
    for _, i in AH[:N]:
        used[i] = True

    h = sum(a for a, _ in AH[:N])
    t = sum(AT)
    m = h - t
    hp = N
    for i in reversed(range(N, 2 * N)):
        t += A[i]
        t += heapq.heappushpop(ATT, -A[i])
        if used[i]:
            h -= A[i]
            while AH[hp][1] > i:
                hp += 1
            h += AH[hp][0]
            used[AH[hp][1]] = True
            hp += 1

        m = max(m, h - t)
    return m

print(main())

Solution (Python):
import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    fl = [i for i in A[:N]]
    f = [sum(A[:N])]
    heapq.heapify(fl)
    ll = [-i for i in A[2*N:]]
    l = [sum(A[2*N:])]
    heapq.heapify(ll)
    for i in range(N):
        s = f[-1]
        if A[N+i] > fl[0]:
            s = s - fl[0] + A[N+i]
            heapq.heappushpop(fl, A[N+i])
        f.append(s)
        s = l[-1]
        if - A[2*N-1-i] > ll[0]:
            s = s + ll[0] + A[2*N-1-i]
            heapq.heappushpop(ll, -A[2*N-1-i])
        l.append(s)
    r = f[0] - l[-1]
    for i in range(N+1):
        r = max(r, f[i] - l[-1-i])
    return r
print(main())

Solution (Python):
import heapq
N = int(input())
*a, = map(int, input().split())

l, r = [], []
for i in range(N):
    heapq.heappush(l, a[i])
    heapq.heappush(r, -a[3*N-i-1])

lsum, rsum = [sum(l)], [sum(r)]
for i in range(N):
    heapq.heappush(l, a[i+N])
    lsum.append(lsum[-1] + a[i+N] - heapq.heappop(l))
    heapq.heappush(r, -a[3*N-i-N-1])
    rsum.append(rsum[-1] - a[3*N-i-N-1] - heapq.heappop(r))

ans = -float('inf')
for i in range(N+1):
    t = lsum[i]+rsum[N-i]
    if ans < t:
        ans = t
print(ans)

Solution (Python):
import heapq
N = int(input())
A = list(map(int,input().split()))
left = [sum(A[:N])]
h1 = A[:N]
heapq.heapify(h1)
for i in range(N):
    heapq.heappush(h1, A[N+i])
    temp = heapq.heappop(h1)
    left.append(left[-1] + A[N+i] - temp)
right = [sum(A[2*N:])]
h2 = list(map(lambda x: -x, A[2*N:]))
heapq.heapify(h2)
for i in range(N):
    heapq.heappush(h2, -A[2*N-1-i])
    temp = -1 * heapq.heappop(h2)
    right.append(right[-1] + A[2*N-1-i] - temp)
ans = float('-inf')
for i in range(N+1):
    ans = max(ans, left[i] - right[-(i+1)])
print(ans)

Solution (Python):
import heapq

data = int(input())
array = [int(_) for _ in input().split()]

X = array[0:data]
B = array[data:2*data]
Y = [-_ for _ in array[2*data:3*data]]

heapq.heapify(X)
heapq.heapify(Y)

x = [sum(X)]
y = [sum(Y)]

for i in range(data):
    x += [B[i] - heapq.heappushpop(X, B[i])]
    y += [-B[-1-i] - heapq.heappushpop(Y, -B[-1-i])]

for i in range(data):
    x[i+1] = x[i]+x[i+1]
    y[i+1] = y[i]+y[i+1]

print(max([x[_] + y[-1 - _] for _ in range(data+1)]))

Solution (Python):
INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    lM = [0] * (n + 1)
    rm = [0] * (n + 1)

    q = []
    cumsum = 0
    for i in range(n):
        heappush(q,a[i])
        cumsum += a[i]
    
    lM[0] = cumsum
    drop = 0
    for i in range(n,2 * n):
        heappush(q,a[i])
        drop += heappop(q)
        cumsum += a[i]
        lM[i - n + 1] = cumsum - drop
    
    q = []
    cumsum = 0
    for i in range(3 * n - 1,2 * n - 1,-1):
        heappush(q,-a[i])
        cumsum += a[i]
    
    rm[-1] = cumsum
    drop = 0
    for i in range(2 * n - 1,n - 1,-1):
        heappush(q,-a[i])
        drop -= heappop(q)
        cumsum += a[i]
        rm[i - n] = cumsum - drop
    
    ans = -INF
    for i in range(n + 1):
        ans = max(ans,lM[i] - rm[i])
        
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m


import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]


n = int(input())
a = list(myinput())


red = a[:n]
blue = a[(2*n):]

s_red = sum(red)
s_blue = sum(blue)

ans = s_red - s_blue


hq_red = Heapq(red,False)

hq_blue = Heapq(blue,True)


ans = -1*float("inf")

ls_s_red = [s_red]
for k in range(n,2*n):
    hq_red.push(a[k])
    p = hq_red.pop()
    s_red = s_red + a[k] - p  
    ls_s_red.append(s_red)


ls_s_blue = [s_blue]
for k in range(n,2*n):
    hq_blue.push(a[-(k+1)])
    p = hq_blue.pop()
    s_blue = s_blue + a[-(k+1)] - p
    ls_s_blue.append(s_blue)
ls_s_blue_sorted = ls_s_blue[::-1]


for k in range(len(ls_s_red)):
    M = ls_s_red[k] - ls_s_blue_sorted[k]
    ans = max(ans,M)

print(ans)

Solution (Python):
from heapq import heapreplace, heapify


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

dp = [0] * (N + 1)
q = A[:N]
heapify(q)
dp[0] = sum(q)
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        dp[i - N + 1] += a - heapreplace(q, a)
    dp[i - N + 1] += dp[i - N]


dp2 = [0] * (N + 1)
q = [-A[i] for i in range(2 * N, 3 * N)]
heapify(q)
dp2[N] = -sum(q)
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        dp2[i - N] += a - (-heapreplace(q, -a))
    dp2[i - N] += dp2[i - N + 1]

ans = -float('inf')
for i in range(N + 1):
    ans = max(ans, dp[i] - dp2[i])
print(ans)

Solution (Python):
from heapq import heappush, heapreplace


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

dp = [0] * (N + 1)
q = []
cnt = 0
for i in range(N):
    a = A[i]
    heappush(q, a)
    cnt += a
dp[0] = cnt
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        cnt += a - heapreplace(q, a)
    dp[i - N + 1] = cnt


dp2 = [0] * (N + 1)
q = []
cnt = 0
for i in range(2 * N, 3 * N):
    a = A[i]
    heappush(q, -a)
    cnt += a
dp2[N] = cnt
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        cnt += a - (-heapreplace(q, -a))
    dp2[i - N] = cnt

ans = -float('inf')
for i in range(N + 1):
    ans = max(ans, dp[i] - dp2[i])
print(ans)

Solution (Python):
import heapq
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = []
    heapq.heapify(q)
    frnt = [None]*3*n
    back = [None]*3*n
    heapq.heappush(q, a[0])
    frnt[0] = a[0]
    for i in range(1, 2*n+1):
        frnt[i] = a[i]
        frnt[i] += frnt[i-1]
        heapq.heappush(q, a[i])
        if n <= i:
            frnt[i] -= heapq.heappop(q)
    q = []
    heapq.heapify(q)
    heapq.heappush(q, -1*a[3*n-1])
    back[3*n-1] = a[3*n-1]
    for i in reversed(range(n-1, 3*n-1)):
        back[i] = a[i]
        back[i] += back[i+1]
        heapq.heappush(q, -1*a[i])
        if i < 2*n:
            back[i] += heapq.heappop(q)
    ans = -float("inf")
    for i in range(n-1, 2*n):
        ans = max(ans, frnt[i] - back[i+1])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
a=list(map(int,input().split()))

left=[0]*(n+1)
right=[0]*(n+1)
left[0]=sum(a[:n])
right[n]=sum(a[n+n:])

mae,usi=a[:n],list(map(lambda x: x*-1,a[n+n:]))

heapq.heapify(mae)
heapq.heapify(usi)

for i in range(n):
    tmp=heapq.heappushpop(mae,a[n+i])
    left[i+1]=left[i]+a[n+i]-tmp
    tmp=heapq.heappushpop(usi,-a[n+n-i-1])
    right[n-i-1]=right[n-i]+a[n+n-i-1]+tmp



ans=-float('inf')
for i in range(n+1):
    ans=max(ans, left[i]-right[i])
print(ans)

Solution (Python):
import sys
import heapq

def main():
	N = int(input())
	a = list(map(int, input().split()))

	left = a[0 : N]
	right = a[N*2 : N*3]

	for i in range(N):
		right[i] *= -1

	left_sum = 0
	right_sum = 0

	heap_left = []
	heap_right = []

	for i in range(N):
		left_sum += left[i]
		heapq.heappush(heap_left, left[i])
		right_sum += right[i]
		heapq.heappush(heap_right, right[i])

	temp1 = [0] * (N + 1)
	temp2 = [0] * (N + 1)

	temp1[0] = left_sum
	temp2[N] = right_sum

	for i in range(0, N):
		left_sum += a[N+i]
		heapq.heappush(heap_left, a[N+i])
		left_sum -= heapq.heappop(heap_left)
		temp1[i+1] = left_sum

	for i in range(0, N):
		right_sum -= a[N*2-1-i]
		heapq.heappush(heap_right, -a[N*2-1-i])
		right_sum -= heapq.heappop(heap_right)
		temp2[N - 1 - i] = right_sum

	ans = -100000000000000000000000000000000000000000
	for i in range(0, N + 1):
		x = temp1[i] + temp2[i]
		if(ans < x):
			ans = x
	print(ans)
main()

Solution (Python):
import heapq
n=int(input())
a=list(map(int,input().split()))
s1=sum(a[:n])
hq1=a[:n]
heapq.heapify(hq1)
A=[s1]
for i in range(n,2*n):
  s1+=a[i]
  heapq.heappush(hq1,a[i])
  x=heapq.heappop(hq1)
  s1-=x
  A.append(s1)
a=a[::-1]
s2=sum(a[:n])
hq2=[-a[i] for i in range(n)]
heapq.heapify(hq2)
B=[s2]
for i in range(n,2*n):
  s2+=a[i]
  heapq.heappush(hq2,-a[i])
  x=heapq.heappop(hq2)
  s2-=-x
  B.append(s2)
B=B[::-1]
ans=-10**18
for i in range(len(A)):
  ans=max(ans,A[i]-B[i])
print(ans)

Solution (Python):
import heapq

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

pre = [0]*(n+1)
pre_list = [e for e in A[:n]]
heapq.heapify(pre_list)
pre_sum = sum(pre_list)
pre[0] = pre_sum
for i in range(n, 2*n):
    small = heapq.heappushpop(pre_list, A[i])
    pre_sum += A[i] - small
    pre[i-n+1] = pre_sum

suf = [0]*(n+1)
suf_list = [-e for e in A[2*n:]]
heapq.heapify(suf_list)
suf_sum = -sum(suf_list)
suf[-1] = suf_sum
for i in range(2*n-1, n-1, -1):
    large = -heapq.heappushpop(suf_list, -A[i])
    suf_sum += A[i] - large
    suf[i-n] = suf_sum




print(max([pre[i] - suf[i] for i in range(n+1)]))

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import *

N = int(input())
a = list(map(int, input().split()))
pq = []
s = 0
minus = [-1]*(N+1)

for i in range(3*N-1, 2*N-1, -1):
    heappush(pq, -a[i])
    s += a[i]

minus[N] = s

for i in range(2*N-1, N-1, -1):
    if a[i]<-pq[0]:
        s -= -heappop(pq)
        heappush(pq, -a[i])
        s += a[i]
    
    minus[i-N] = s

pq = []
s = 0

for i in range(N):
    heappush(pq, a[i])
    s += a[i]

ans = s-minus[0]

for i in range(N, 2*N):
    if a[i]>pq[0]:
        s -= heappop(pq)
        heappush(pq, a[i])
        s += a[i]
    
    ans = max(ans, s-minus[i-N+1])

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
import heapq as hq
f1=[0]*(3*n)
f1[n-1]=sum(a[:n])
h=a[:n]
hq.heapify(h)
su=f1[n-1]
for i in range(n,2*n):
    cur=a[i]
    x=hq.heappop(h)
    if cur>x:
        su-=x
        su+=cur
        hq.heappush(h,cur)
    else:
        hq.heappush(h,x)
    f1[i]=su
f2=[0]*(3*n)
f2[2*n]=sum(a[2*n:])
su=f2[2*n]
h2=[]
for i in a[2*n:]:
    h2.append(-i)
hq.heapify(h2)
for i in range(2*n-1,n-1,-1):
    cur=a[i]
    x=-1*hq.heappop(h2)
    if cur<x:
        su-=x
        su+=cur
        hq.heappush(h2,-cur)
    else:
        hq.heappush(h2,-x)
    f2[i]=su
ans=-float('inf')
for i in range(n-1,2*n):
    ans=max(ans,f1[i]-f2[i+1])
print(ans)

Solution (Python):

import heapq 
n = int(input())
An = list(map(int, input().split()))
former = An[:n]
latter = An[2*n:]
latter = list(map(lambda x:-x, latter))
heapq.heapify(former)
heapq.heapify(latter)

sum_former = sum(former)
sum_latter = sum(latter)

former_list = [0]*(n+1) 
latter_list = [0]*(n+1) 
former_list[0] = sum_former 
latter_list[0] = sum_latter 

for i in range(n, 2*n):
  heapq.heappush(former, An[i])
  m = heapq.heappop(former)
  former_list[i-n+1] = former_list[i-n] + An[i] - m 

for i in range(2*n-1, n-1, -1):
  heapq.heappush(latter, -An[i])
  m = heapq.heappop(latter)
  latter_list[2*n-i] = latter_list[2*n-i-1] - An[i] - m

latter_list.reverse()
ans = -float('inf')
for i in range(n+1):
  ans = max(ans, former_list[i]+latter_list[i])
print(ans)

Solution (Python):
import heapq
n = int(input())
a = list(map(int, input().split()))

h = a[:n]
heapq.heapify(h)
first = [0] * (n+1)
s = sum(a[:n])
first[0] = s
for i in range(n):
    s += a[n+i]
    heapq.heappush(h, a[n+i])
    s -= heapq.heappop(h)
    first[i+1] = s

h = list(map(lambda x: -x, a[2*n:]))
heapq.heapify(h)
second = [0] * (n+1)
s = - sum(a[2*n:])
second[0] = s
for i in range(n):
    s -= a[2*n - i - 1]
    heapq.heappush(h, -a[2*n - i - 1])
    s -= heapq.heappop(h)
    second[i+1] = s

ans = - 10 ** 18
for i in range(n+1):
    ans = max(ans, first[i] + second[n-i])
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

b = list(enumerate(a))

l = sorted(b[:2*n], key=lambda x: x[1], reverse=True)
r = sorted(b[n:], key=lambda x: x[1])

big = [0] * (3*n)
small = [0] * (3*n)

for i, (pos, z) in enumerate(l):
    big[pos] = i
for i, (pos, z) in enumerate(r):
    small[pos] = i

first = sum(a[:n])
second = 0
for pos, z in r[:n]:
    second += z
i = 2 * n
j = n-1
ans = first - second
for split in range(n, 2*n):
    if big[split] < i:
        first += a[split]
        i -= 1
        while l[i][0] > split:
            i -= 1
        first -= l[i][1]
    if small[split] <= j:
        second -= a[split]
        j += 1
        while r[j][0] < split:
            j += 1
        second += r[j][1]
    ans = max(ans, first - second)
print(ans)

Solution (Python):
import heapq
N=int(input())
a=list(map(int,input().split()))
l=[None]*(N+1)
r=[None]*(N+1)
h=a[:N]
s=sum(h)
heapq.heapify(h)
l[0]=s
for i in range(N):
    heapq.heappush(h,a[i+N])
    s+=a[i+N]-heapq.heappop(h)
    l[i+1]=s
h=list(map(lambda x:-x,a[2*N:]))
heapq.heapify(h)
s=sum(h)
r[-1]=s
for i in range(N):
    heapq.heappush(h,-a[-N-i-1])
    s+=-a[-N-i-1]-heapq.heappop(h)
    r[-i-2]=s
a=l[0]+r[0]
for i in range(1,N+1):
    if a<l[i]+r[i]:
        a=l[i]+r[i]
print(a)