Indian National Olympiad in Informatics 2015
In this problem you are given two lists of N integers, a1, a2, ..., aN and b1, b2, ... bN. For any pair (i, j) with i, j ϵ {1, 2, ..., N} we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j. Thus if N = 5 then the [2, 4] = {2, 3, 4} and [4, 2] = {4, 5, 1, 2}.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
- SSum[i, i] = ai.
- If i ≠ j then, 

The positions i and j contribute ai and aj, respectively, to the sum while every other position k in [i, j] contributes bk.
Suppose N = 5 and that the two given sequences are as follows:
i
1
2
3
4
5
ai
2
3
2
3
1
bi
3
4
4
6
3

Then, SSum[1, 1] = 2, SSum[2, 4] = 3 + 4 + 3 = 10 and SSum[4, 2] = 3 + 3 + 3 + 3 = 12. Your aim is to compute the maximum value of SSum[i, j] over all segments [i, j]. In this example you can verify that this value is 18 (SSum[2, 1] = 18).

-----Input format-----
- The first line contains a single positive integer N.
- This is followed by a line containing N integers giving the values of the ais and this is followed by a line containing N integers giving the values of the bis.

-----Output format-----
A single integer in a single line giving the maximum possible special segment sum.
Note: The final value may not fit in a 32 bit integer. Use variables of an appropriate type to store and manipulate this value (long long in C/C++, long in Java).

-----Test Data-----
You may assume that -109 ≤ ai, bi ≤ 109.
Subtask 1 (10 Marks) 1 ≤ N ≤ 3000.
Subtask 2 (20 Marks) 1 ≤ N ≤ 106 and ai = bi for all 1 ≤ i ≤ N.
Subtask 3 (30 Marks) 3 ≤ N ≤106. Further a1 = b1 = aN = bN = -109 and for each
1 < k < N we have -999 ≤ ak, bk ≤ 999.
Subtask 4 (40 Marks) 1 ≤ N ≤ 106.

-----Example-----
Here is the sample input and output corresponding to the example above:

-----Sample input-----
5
2 3 2 3 1
3 4 4 6 3

-----Sample output-----
18

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "#dt = {} for i in x: dt[i] = dt.get(i,0)+1\r\nimport sys;input = sys.stdin.readline\r\n#import io,os; input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline #for pypy\r\ninp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]\r\n\r\nfrom collections import deque\r\ndef getmax(x,n,k):\r\n    mx = []\r\n    dq = deque()\r\n    for i in range(k):\r\n        while dq and x[i] >= x[dq[-1]]:\r\n            dq.pop()\r\n        dq.append(i)\r\n    mx.append(x[dq[0]])\r\n    for i in range(k,n):\r\n        while dq and dq[0] <= i-k:\r\n            dq.popleft() \r\n        while dq and x[i] >= x[dq[-1]]:\r\n            dq.pop()\r\n        dq.append(i)\r\n        mx.append(x[dq[0]])\r\n    return mx\r\n\r\nn = inp()\r\nm = n+n\r\nA = ip()\r\nB = ip()\r\nA += A\r\nB += B\r\npre = [0]*(m+1)\r\nfor i in range(1,m+1):\r\n    pre[i] += pre[i-1] + B[i-1]\r\nplus = [0]*m\r\nminus = [0]*m\r\nfor i in range(m):\r\n    plus[i] = A[i]+pre[i]\r\n    minus[i] = A[i]-pre[i+1]\r\na = getmax(plus,m,n-1)\r\nans = float('-inf')\r\nfor i in range(n):\r\n    ans = max(ans,minus[i]+a[i+1])\r\nprint(max(ans,*A))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: