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.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Runtime Error

Solution code:
import math


class MyHeap:
    def __init__(self, normal_list, smaller=True):
        self.smaller = smaller
        self.length = 0
        self.list = []
        for item in normal_list:
            self.heap_push(item)

    def heap_pop(self):
        top = self.list[0]
        bottom = self.list.pop()
        if top == bottom:
            return top
        self.length = len(self.list)
        self.list[0] = bottom
        current_index = 0
        while not self.is_bottom(current_index):
            left_child_index = current_index * 2 + 1
            right_child_index = current_index * 2 + 2
            if right_child_index >= self.length:
                prior_child_index = left_child_index
            else:
                prior_child_index = self.get_prior_index(left_child_index, right_child_index)
            if self.is_prior_index(prior_child_index, current_index):
                self.swap(prior_child_index, current_index)
                current_index = prior_child_index
            else:
                break

        return top

    def heap_push(self, item):
        self.list.append(item)
        self.length = len(self.list)
        current_index = self.length - 1
        while current_index != 0:
            parent_index = self.get_parent_index(current_index)
            if self.is_prior_index(current_index, parent_index):
                self.swap(current_index, parent_index)
                current_index = parent_index
            else:
                break

    def is_bottom(self, index):
        return index * 2 + 1 >= self.length

    def is_prior(self, a, b):
        less_than_bool = a <= b
        if self.smaller:
            return less_than_bool
        else:
            return not less_than_bool

    def is_prior_index(self, a_index, b_index):
        return self.is_prior(self.list[a_index], self.list[b_index])

    def get_prior_index(self, a_index, b_index):
        if self.is_prior_index(a_index, b_index):
            return a_index
        else:
            return b_index

    def swap(self, a_index, b_index):
        a_value = self.list[a_index]
        b_value = self.list[b_index]
        self.list[a_index] = b_value
        self.list[b_index] = a_value

    def get_parent_index(self, index):
        if index % 2 == 0:
            return index // 2 - 1
        else:
            return (index - 1) // 2


if __name__ == '__main__':
    n = int(input())
    raw_input = list(map(int, input().split()))
    left_list = raw_input[0:n]
    middle_list = raw_input[n:2 * n]
    right_list = raw_input[2 * n:3 * n]
    left_queue = MyHeap(left_list)
    right_queue = MyHeap(right_list, False)

    ans_left_list = [sum(left_queue.list)]
    ans_right_list = [sum(right_queue.list)]

    for i in range(n):
        left_queue.heap_push(middle_list[i])
        left_queue.heap_pop()
        ans_left_list.append(sum(left_queue.list))

        right_queue.heap_push(middle_list[n - i - 1])
        right_queue.heap_pop()
        ans_right_list.append(sum(right_queue.list))

    ans_right_list = list(reversed(ans_right_list))

    ans = -math.inf

    for i in range(n):
        diff = ans_left_list[i] - ans_right_list[i]
        if ans < diff:
            ans = diff

    print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *

N=int(input())
A=map(int,input().split())
A.reverse()
B=[]
heap=[]
for i in range(N):
    heappush(heap,A[i])
for i in range(N,2*N):
    if heap[0]<A[i]:
        B.append(heappop(heap))
        heappush(heap,A[i])
    else:
        B.append(A[i])
C=[]
for i in range(2*N,3*N):
    if 2*B[-1]-A[i]-heap[0]>0:
        C.append(B.pop(-1))
        B.append(heappop(heap))
    else:
        C.append(A[i])
print(sum(C)-sum(B))

Submission status: Runtime Error

Solution code:
import heapq
n= int(input())
a=[int(i) for i in input().split()]
heap1=[]
heap2=[]
a_max=[]
b_max=[]
s=0
for i in range(n):
    heapq.heappush(heap1, a[i])
    s+=a[i]
a_max.append(s)
for i in range(n):
    heapq.heappush(heap1,a[n+i])
    mini=heapq.heappop(heap1)
    s=s+a[n+i]-mini
    a_max.append(s)
s=0
for i in range(n):
    heapq.heappush(heap2,-a[2*n+i])
    s=s-a[2*n+i]
b_max.append(s)    
for i in range(n):
    heapq.heappush(heap2,-a[2*n-1-i])
    mini=heapq.heappop(heap2)
    s=s-a[2*n-1-i]-mini
    b_max.append(s)
ans=a_max[2]+b_max[-3]
for i in range(n):
    res=a_max[i]+b_max[-(i+1)]
    ans=max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
b=list(map(int,input().split()))
m=0
sd1=[]
sd2=[]
"""
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1
"""
d1=b[:N]
sd1.append(sum(d1))
d2=b[2*N:]
sd2.append(sum(d2))
Max=sum(d1)-sum(d2)
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
    if max(d2) > b[2*N-m]:
        d2.remove((max(d2)))
        d2.append(b[2*N-m])

    sd1.append(sd1[m]-min(d1)+b[N+m])
    sd2.append(sd2[N-m-1]-max(d2)+b[2*N-m])
    if Max < (sd1[m+1]+sd2[N-m]):
            Max=sum(d1)-sum(d2)
    m+=1

print(Max)

Submission status: Runtime Error

Solution code:
N=int(input())
b=list(map(int,input().split()))
Max=[]
m=0
"""
while m <= N:
    #d1=heapq.nlargest(N,b[:2*N-m])
    d1=sorted(b[:2*N-m], reverse=True)[:N]
    #d2=heapq.nsmallest(N,b[2*N-m:])
    d2=sorted(b[2*N-m:])[:N]
    Max.append(sum(d1)-sum(d2))
    m+=1
"""
d1=b[:N]
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
        d2=sorted(b[N+m+1:])[:N]
        Max.append(sum(d1)-sum(d2))
    m+=1

print(max(Max))

Submission status: Runtime Error

Solution code:
N=int(input())
b=list(map(int,input().split()))
Max=[]
m=0

d1=b[:N]
while m<N:
    if min(d1) < b[N+m]:
        d1.remove((min(d1)))
        d1.append(b[N+m])
        d2=sorted(b[N+m+1:])[:N]
        Max.append(sum(d1)-sum(d2))
    m+=1

print(max(Max))

Submission status: Runtime Error

Solution code:
import heapq
import bisect

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

big = a[0:n//3]
big.sort()
tempmin = a[n//3::]
tempmin.sort()
small = tempmin[0:n//3]
spare = tempmin[n//3::]

ans = sum(big)-sum(small)
mxm = ans

heapq.heapify(small)
heapq.heapify(spare)

for i in range(n//3,2*n//3):
    if len(spare) != 0 and a[i] >= spare[0]:
        index = bisect.bisect_left(spare,a[i])
        spare.pop(index)

    if a[i] > big[0]:
        ans += a[i]-big[0]
        index = bisect.bisect_left(big,a[i])
        big.insert(index,a[i])
        big.pop(0)
    
    if a[i] <= small[-1]:
        ans -= spare[0]-a[i]
        heapq.heappush(small,spare[0])
        heapq.heappop(spare)
        index = bisect.bisect_left(small,a[i])
        small.pop(index)
    
    if ans > mxm:
        mxm = ans
print(mxm)

Submission status: Runtime Error

Solution code:
import heapq
import bisect

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

big = a[0:n//3]
tempmin = a[n//3::]
tempmin.sort()
small = tempmin[0:n//3]
spare = tempmin[n//3::]

ans = sum(big)-sum(small)
mxm = ans

heapq.heapify(small)
heapq.heapify(spare)

for i in range(n//3,2*n//3):
    if len(spare) != 0 and a[i] >= spare[0]:
        index = bisect.bisect_left(spare,a[i])
        spare.pop(index)

    if a[i] > big[0]:
        ans += a[i]-big[0]
        index = bisect.bisect_left(big,a[i])
        big.insert(index,a[i])
        big.pop(0)
    
    if a[i] < small[-1]:
        ans -= spare[0]-a[i]
        heapq.heappush(small,spare[0])
        heapq.heappop(spare)
        index = bisect.bisect_left(small,a[i])
        small.pop(index)
    
    if ans > mxm:
        mxm = ans
print(mxm)

Submission status: Runtime Error

Solution code:
import bisect

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

big = a[0:n//3]
tempmin = a[n//3::]
tempmin.sort()
small = tempmin[0:n//3]

spare = tempmin[n//3:]


big.sort()
small.sort()
ans = sum(big)-sum(small)

mxm = ans
for i in range(n//3,2*n//3):
    if a[i] > big[0]:
        ans += a[i]-big[0]
        index = bisect.bisect_left(big,a[i])
        big.insert(index,a[i])
        big.pop(0)
    if a[i] <= small[-1]:
        index = bisect.bisect_left(spare,a[i])
        ans -= spare[index] - a[i]
        aindex = bisect.bisect_left(small,spare[index])
        small.insert(aindex,spare[index])
        aindex = bisect.bisect_left(small,a[i])
        small.pop(aindex)
        spare.pop(index)

    if len(spare) != 0 and a[i] >= spare[0]:
        index = bisect.bisect_left(spare,a[i])
        spare.pop(index)

    if ans > mxm:
        mxm = ans
print(mxm)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)


def solve(N, a):
    a_lef = a[0:N]
    heapq.heapify(a_lef)
    sum_lef = sum(a_lef)
    l_sum_lef = [sum_lef]

    for i in range(N, 2 * N):
        sum_lef += a[i]
        heapq.heappush(a_lef, a[i])
        num_pop = heapq.heappop(a_lef)
        sum_lef -= num_pop
        l_sum_lef.append(sum_lef)

    a_rig = a[2 * N:3 * N]
    heapq._heapify_max(a_rig)
    sum_rig = sum(a_rig)
    l_sum_rig = [sum_rig]

    for i in range(2 * N - 1, N - 1, -1):
        if a[i] >= a_rig[0]:
            l_sum_rig.append(sum_rig)
        else:
            sum_rig += a[i]
            num_pop = heapq._heapreplace_max(a_rig, a[i])
            sum_rig -= num_pop
            l_sum_rig.append(sum_rig)

    ans = INF * -1

    for i in range(N + 1):
        num_dif = l_sum_lef[i] - l_sum_rig[N - i]
        ans = max(ans, num_dif)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import Counter

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A[N:])
  selected_right = Counter(temp[:N])
  unselected_right_counter = Counter(temp[N:])
  unselected_right = list(unselected_right_counter.keys()) # min heap
  heapify(unselected_right)


  r_score = sum(selected_right)

  yield l_score-r_score

  for i,a in enumerate(A[N:2*N]):
    # left 使うものを減らす, right 使うものを増やす
    l_score -= heappushpop(selected_left, a)
    l_score += a
      
    if selected_right[a] > 0:
      r_score -= a
      selected_right[a] -= 1

      x = unselected_right[0]
      while unselected_right_counter[x] == 0:
        del unselected_right_counter[x]
        x = heappop(unselected_right)

      unselected_right_counter[x] -= 1
      selected_right[x] += 1
      r_score += x
    else:
      del selected_right[a]
      unselected_right_counter[a] -= 1

    yield l_score-r_score

print(max(scores()))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))

def exmax(x, y):
    if x is None:
        return y
    elif y is None:
        return x
    else:
        return max(x, y)

memo = [None] * ((1 << 3 * N) + 1)
def r(n, k, b):
    if 3 * N - n < N - k:
        return None
    elif memo[b] is not None:
        return memo[b]
    elif k == N:
        sf, sb = 0, 0
        count = 0
        f = 1
        for i in range(3 * N):
            if not f & b:
                if count < N:
                    sf += a[i]
                    count += 1
                else:
                    sb += a[i]
            elif f > b:
                break
            f <<= 1
        ans = sf - sb
    else:
        ans = exmax(r(n + 1, k + 1, b | (1 << n)), r(n + 1, k, b))

    memo[b] = ans
    return ans

print(r(0, 0, 0))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    a = ILI()
    return (N, a)

def solve(N, a):
    a_lef = a[0:N]
    a_mid = a[N:2 * N]
    a_rig = a[2 * N : 3 * N]
    heapq.heapify(a_lef)
    heapq._heapify_max(a_rig)

    i_lef = 0
    i_rig = N - 1

    for __ in range(N):
        n_lef = a_lef[0] * -1 + a_mid[i_lef]
        n_rig = a_rig[0] - a_mid[i_rig]
        if n_lef >= n_rig:
            heapq.heappop(a_lef)
            heapq.heappush(a_lef, a_mid[i_lef])
            i_lef += 1
        else:
            heapq._heapreplace_max(a_rig, a_mid[i_rig])
            i_rig -= 1

    ans = sum(a_lef) - sum(a_rig)
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

INF=-100000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])

ans=INF
left=sum(before)
right=sum(after[:N])
borderR=after[N-1]
for i in range(N):
	ans=max(ans,left-right)
	
	temp=a[N+i]
	
	after.remove(temp)
	if temp<=borderR:
		right-=temp
		right+=after[N-1]
		
	if before[0]<temp:
		left-=before.pop(0)
		left+=temp
		for j in range(N):
			if temp<before[i]:
				before.insert(i,temp)
				break
		if len(before)!=N:
			before.append(temp)
			
			
left=sum(before)
right=sum(after[:N])
ans=max(ans,left-right)
print(ans)

Submission status: Runtime Error

Solution code:
# D
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

# pop from left
popleft = [0]*(N+1)
A_LEFT = np.argsort(A[:(2*N)])
ind_left = 1
for i in range(N):
    while popleft[ind_left] > 0:
        ind_left += 1
    if A_LEFT[i] < N:
        popleft[ind_left] = A[A_LEFT[i]]
    else:
        popleft[A_LEFT[i] - (N-2)] = A[A_LEFT[i]]
left_sum = np.cumsum(A)[(N-1):2*N] - np.cumsum(np.array(popleft))

# pop from right
popright = [0]*(N+1)
A_RIGHT = np.argsort(-A[::-1][:(2*N)])
ind_right = 1
for i in range(N):
    while popright[ind_right] > 0:
        ind_right += 1
    if A_RIGHT[i] < N:
        popright[ind_right] = A[3*N - 1 - A_RIGHT[i]]
    else:
        popright[A_RIGHT[i] - (N-2)] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):2*N] - np.cumsum(np.array(popright))

# print(popleft)
# print(popright)
res = (left_sum - right_sum[::-1]).max()
# extreme case
res1 = (np.sort(A[:2*N])[N:]).sum() - A[2*N:].sum()
res2 = A[:N].sum() - (np.sort(A[N:])[:N]).sum()
print(max(res, res1, res2))

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

INF=-100000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])

ans=INF
borderR=after[N-1]
for i in range(N):
	ans=max(ans,left-right)
	
	temp=a[N+i]
	
	after.remove(temp)
	if temp<=borderR:
		right-=temp
		right+=after[N-1]
		
	if before[0]<temp:
		left-=before.pop(0)
		left+=temp
		for j in range(N):
			if temp<before[i]:
				before.insert(i,temp)
				break
		if len(before)!=N:
			before.append(temp)
			
			
left=sum(before)
right=sum(after[:N])
ans=max(ans,left-right)
print(ans)

Submission status: Runtime Error

Solution code:
# D
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

# pop from left
popleft = [0]*(N+1)
A_LEFT = np.argsort(A[:(2*N)])
ind_left = 1
for i in range(N):
    while popleft[ind_left] > 0:
        ind_left += 1
    if A_LEFT[i] < N:
        popleft[ind_left] = A[A_LEFT[i]]
    else:
        popleft[A_LEFT[i] - (N-2)] = A[A_LEFT[i]]
left_sum = np.cumsum(A)[(N-1):2*N] - np.cumsum(np.array(popleft))

# pop from right
popright = [0]*(N+1)
A_RIGHT = np.argsort(-A[::-1][:(2*N-1)])
ind_right = 1
for i in range(N):
    while popright[ind_right] > 0:
        ind_right += 1
    if A_RIGHT[i] < N:
        popright[ind_right] = A[3*N - 1 - A_RIGHT[i]]
    else:
        popright[A_RIGHT[i] - (N-2)] = A[3*N - 1 - A_RIGHT[i]]
right_sum = np.cumsum(A[::-1])[(N-1):2*N] - np.cumsum(np.array(popright))

# print(popleft)
# print(popright)
res = (left_sum - right_sum[::-1]).max()
# extreme case
res1 = (np.sort(A[:2*N])[N:]).sum() - A[2*N:].sum()
res2 = A[:N].sum() - (np.sort(A[N:])[:N]).sum()
print(max(res, res1, res2))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))

def exmax(x, y):
    if x is None:
        return y
    elif y is None:
        return x
    else:
        return max(x, y)

memo = [None] * ((1 << 3 * N) + 1)
def r(n, k, b):
    if 3 * N - n < N - k:
        return None
    elif memo[b] is not None:
        return memo[b]
    elif k == N:
        sf, sb = 0, 0
        count = 0
        for i in range(3 * N):
            if not (1 << i) & b:
                if count < N:
                    sf += a[i]
                    count += 1
                else:
                    sb += a[i]
        ans = sf - sb
    else:
        ans = exmax(r(n + 1, k + 1, b | (1 << n)), r(n + 1, k, b))

    memo[b] = ans
    return ans

print(r(0, 0, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))

def exmax(x, y):
    if x is None:
        return y
    elif y is None:
        return x
    else:
        return max(x, y)


def r(n, k, b):
    if 3 * N - n < N - k:
        return None
    elif k == N:
        sf, sb = 0, 0
        count = 0
        for i in range(3 * N):
            if not (1 << i) & b:
                if count < N:
                    sf += a[i]
                    count += 1
                else:
                    sb += a[i]
#            elif f > b:
#                break
#            f <<= 1
        ans = sf - sb
    else:
        ans = exmax(r(n + 1, k + 1, b | (1 << n)), r(n + 1, k, b))

    return ans

print(r(0, 0, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))

def exmax(x, y):
    if x is None:
        return y
    elif y is None:
        return x
    else:
        return max(x, y)


memo = [None] * (1 << 3 * N)
def r(n, k, b):
    if 3 * N - n < N - k:
        return None
    elif memo[b] is not None:
        return memo[b]
    elif k == N:
        sf, sb = 0, 0
        count = 0
        for i in range(3 * N):
            if not (1 << i) & b:
                if count < N:
                    sf += a[i]
                    count += 1
                else:
                    sb += a[i]
#            elif f > b:
#                break
#            f <<= 1
        ans = sf - sb
    else:
        ans = exmax(r(n + 1, k + 1, b | (1 << n)), r(n + 1, k, b))

    memo[b] = ans
    return ans

print(r(0, 0, 0))

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

INF=-100000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	after.remove(a[N+i])
	if before[0]<a[N+i]:
		before.pop(0)
		for j in range(N):
			if a[N+i]<before[i]:
				before.insert(i,a[N+i])
				break
		if len(before)!=N:
			before.append(a[N+i])
			
			
left=sum(before)
right=sum(after[:N])
ans=max(ans,left-right)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n = int(input())
xs = list(map(int, input().split()))
head = heapq.heapify(xs[:n])
body = xs[n:2*n]
body_and_tail = sorted(xs[n:])
sum_tail = sum(body_and_tail_list[:n])
unused_tail = heapq.heapify(body_and_tail[-n:])
ans = -1000000000000000000000
temp = sum(head) - sum_tail
for b in body:
    heapq.push(head, b)
    temp = temp - heapq.pop(head) - heapq.pop(unused_tail) + 2*b
    ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

INF=-10000000000000000

#前方Nと後方2Nで分割かつソート
before=sorted(a[:N])
after=sorted(a[N:])
#print(before)
#print(after)

ans=INF
for i in range(N):
	left=sum(before)
	right=sum(after[:N])
	ans=max(ans,left-right)
	
	del after[N+i]
	if before[0]<a[N+i]:
		del before[0]
		before.append(a[N+i])
		before.sort()
	
	#print(before)
	#print(after)
	#print()
ans=max(ans,left-right)
print(ans)