Background

中欧班列（英文名称：“CHINA RAILWAY Express”，缩写：“CR Express”）是由中国国家铁路集团有限公司组织，按照固定车次、线路、班期和全程运行时刻开行，运行于中国与欧洲以及“一带一路”共建国家间的集装箱等铁路国际联运列车，是深化国家与沿线国家经贸合作的重要载体和推进“一带一路”建设的重要抓手。^ [344]^

中欧班列往来于中国与欧洲及一带一路沿线各国的集装箱国际铁路联运班列。铺划了西中东3条通道中欧班列运行线：西部通道由国家中西部经阿拉山口（霍尔果斯）出境，中部通道由国家华北地区经二连浩特出境，东部通道由中国东北地区经满洲里（绥芬河）出境。

2023年上半年，中欧班列累计开行8641列，发送货物93.6万标箱。^ [507]^7月29日，随着中欧班列（义乌—马德里）从义乌西站开出，2023年中欧班列累计开行10000列^ [517]^。截至2023年12月15日，中欧班列（长安号）已累计开行21193列，2023年已开行5139列。西安成为全国首个中欧班列年度开行量突破5000列、累计开行量超过20000列的城市。^ [574]^2024年前两个月，广东中欧班列进出口开行国际班列166列，同比增长5%。^ [611]^

中欧班列（中豫号）是河南省融入“一带一路”建设的重要平台，2023年是河南开行中欧班列的第10年。^ [543]^

2024年11月15日，X8083次中欧班列从重庆团结村中心站开车，中欧班列累计开行突破10万列，发送货物超1100万标箱，货值超4200亿美元。^ [634]^^ [652]^^ [729]^^ [750]^^ [799]^^ [801]^2024年，中欧班列(武汉)折算发运1008列。^ [840]^2024年，天津海关共监管发运天津中欧、中亚班列突破600列、6万标箱。^ [846]^

Description

显然这么长的距离不可能一个司机开到底，那么问题来了，如果现在有4位火车司机，在单司机值乘模式下，每个司机开一段路，如何分配使得司机之间里程差的最大值最小。

Format

Input

第一行一个正整数 $N（\le2\times10^5）$，表示从起点到终点一共有 $N+1$ 个车站。

第二行有 $N$ 个不超过 $10^9$ 的正整数，表示从起点站到终点站，每两个相邻站点之间的里程数。

Output

一个整数，表示里程差的最大值最小值。

Samples

7
1 2 3 114514 4 5 6

114508

Limitation

1s, 1024KiB for each test case.