program c
implicit none
integer(8) :: n,i,cut2,b1,c1,b2,c2,d1,e1,d2,e2,tmp1,tmp2,tmp3,tmp4
integer(8),parameter :: ten = 10
integer(8) :: ans = ten ** 15.
integer(8) :: a(200000)=0,s(200000)=0
integer(8) :: low,high,mid
double precision :: target

read(*,*) n
read(*,*) (a(i),i=1,n)

!まず累計和をとる
do i=1,n
	if(i == 1) then
		s(i) = a(i)
	else
		s(i) = s(i-1) + a(i)
	endif
enddo

!部分列Cの末尾のiをcut2とする
do cut2 = 2,n-2

	!部分列Bの末尾を2分探査する
	low = 1
	high = cut2-1
	target = s(cut2)/2.
	
	do while(low <= high)
		mid = (low + high) / 2
		if (s(mid) > target) then
			high = mid - 1
		else
			low = mid + 1
		endif
	enddo
	
	if(s(mid) > target) then
		mid = mid - 1
	endif
	
	b1 = s(max(mid,1))
	c1 = s(cut2)-b1
	b2 = s(min(mid+1,cut2-1))
	c2 = s(cut2)-b2

	!同様に部分列Dの末尾を2分探査する
	!部分列Bの末尾を2分探査する
	low = cut2+1
	high = n-1
	target = (s(n)-s(cut2))/2.
	
	do while(low <= high)
		mid = (low + high) / 2
		if (s(mid)-s(cut2) > target) then
			high = mid - 1
		else
			low = mid + 1
		endif
	enddo
	
	if(s(mid)-s(cut2) > target) then
		mid = mid - 1
	endif
	
	d1 = s(max(mid,cut2+1))-s(cut2)
	e1 = s(n)-s(cut2)-d1
	d2 = s(min(mid+1,n-1))-s(cut2)
	e2 = s(n)-s(cut2)-d2
	tmp1 = max(b1,c1,d1,e1)-min(b1,c1,d1,e1)
	tmp2 = max(b2,c2,d2,e2)-min(b2,c2,d2,e2)
	tmp3 = max(b1,c1,d2,e2)-min(b1,c1,d2,e2)
	tmp4 = max(b2,c2,d1,e1)-min(b2,c2,d1,e1)
	ans = min(ans,tmp1,tmp2,tmp3,tmp4)
	
enddo

	write(*,*) ans

end program
; ModuleID = 'FIRModule'
source_filename = "FIRModule"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@_QFEa = internal global [200000 x i64] zeroinitializer
@_QFEans = internal unnamed_addr global i64 999999986991104
@_QFEs = internal unnamed_addr global [200000 x i64] zeroinitializer
@_QQcl.1798884dfd1b212b4237fe99fdbff199 = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_5801/source.f\00"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

define void @_QQmain() local_unnamed_addr {
  %1 = alloca i64, align 8
  %2 = tail call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.1798884dfd1b212b4237fe99fdbff199, i32 10)
  %3 = call i1 @_FortranAioInputInteger(ptr %2, ptr nonnull %1, i32 8)
  %4 = call i32 @_FortranAioEndIoStatement(ptr %2)
  %5 = call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.1798884dfd1b212b4237fe99fdbff199, i32 11)
  %6 = load i64, ptr %1, align 8, !tbaa !3
  %7 = icmp sgt i64 %6, 0
  br i1 %7, label %.lr.ph, label %._crit_edge

.lr.ph:                                           ; preds = %0, %.lr.ph
  %8 = phi i64 [ %12, %.lr.ph ], [ 1, %0 ]
  %9 = add nsw i64 %8, -1
  %10 = getelementptr [200000 x i64], ptr @_QFEa, i64 0, i64 %9
  %11 = call i1 @_FortranAioInputInteger(ptr %5, ptr %10, i32 8)
  %12 = add nuw i64 %8, 1
  %exitcond.not = icmp eq i64 %8, %6
  br i1 %exitcond.not, label %._crit_edge, label %.lr.ph

._crit_edge:                                      ; preds = %.lr.ph, %0
  %13 = call i32 @_FortranAioEndIoStatement(ptr %5)
  %14 = load i64, ptr %1, align 8, !tbaa !3
  %15 = icmp sgt i64 %14, 0
  br i1 %15, label %16, label %._crit_edge88

16:                                               ; preds = %._crit_edge
  %17 = load i64, ptr @_QFEa, align 16
  store i64 %17, ptr @_QFEs, align 16, !tbaa !3
  %exitcond123.peel.not = icmp eq i64 %14, 1
  br i1 %exitcond123.peel.not, label %._crit_edge88.thread, label %.peel.next.preheader

.peel.next.preheader:                             ; preds = %16
  %load_initial = load i64, ptr @_QFEs, align 16
  %18 = add i64 %14, -1
  %xtraiter = and i64 %18, 1
  %19 = icmp eq i64 %14, 2
  br i1 %19, label %._crit_edge88.loopexit.unr-lcssa, label %.peel.next.preheader.new

.peel.next.preheader.new:                         ; preds = %.peel.next.preheader
  %unroll_iter = and i64 %18, -2
  br label %.peel.next

.peel.next:                                       ; preds = %.peel.next, %.peel.next.preheader.new
  %store_forwarded = phi i64 [ %load_initial, %.peel.next.preheader.new ], [ %28, %.peel.next ]
  %20 = phi i64 [ 2, %.peel.next.preheader.new ], [ %30, %.peel.next ]
  %niter = phi i64 [ 0, %.peel.next.preheader.new ], [ %niter.next.1, %.peel.next ]
  %21 = add nsw i64 %20, -1
  %22 = getelementptr [200000 x i64], ptr @_QFEa, i64 0, i64 %21
  %23 = load i64, ptr %22, align 8, !tbaa !3
  %24 = add i64 %23, %store_forwarded
  %25 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %21
  store i64 %24, ptr %25, align 8, !tbaa !3
  %26 = getelementptr [200000 x i64], ptr @_QFEa, i64 0, i64 %20
  %27 = load i64, ptr %26, align 16, !tbaa !3
  %28 = add i64 %27, %24
  %29 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %20
  store i64 %28, ptr %29, align 16, !tbaa !3
  %30 = add nuw i64 %20, 2
  %niter.next.1 = add i64 %niter, 2
  %niter.ncmp.1 = icmp eq i64 %niter.next.1, %unroll_iter
  br i1 %niter.ncmp.1, label %._crit_edge88.loopexit.unr-lcssa.loopexit, label %.peel.next, !llvm.loop !7

._crit_edge88.loopexit.unr-lcssa.loopexit:        ; preds = %.peel.next
  %31 = or i64 %20, 1
  br label %._crit_edge88.loopexit.unr-lcssa

._crit_edge88.loopexit.unr-lcssa:                 ; preds = %._crit_edge88.loopexit.unr-lcssa.loopexit, %.peel.next.preheader
  %store_forwarded.unr = phi i64 [ %load_initial, %.peel.next.preheader ], [ %28, %._crit_edge88.loopexit.unr-lcssa.loopexit ]
  %.unr = phi i64 [ 1, %.peel.next.preheader ], [ %31, %._crit_edge88.loopexit.unr-lcssa.loopexit ]
  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
  br i1 %lcmp.mod.not, label %._crit_edge88, label %.peel.next.epil

.peel.next.epil:                                  ; preds = %._crit_edge88.loopexit.unr-lcssa
  %32 = getelementptr [200000 x i64], ptr @_QFEa, i64 0, i64 %.unr
  %33 = load i64, ptr %32, align 8, !tbaa !3
  %34 = add i64 %33, %store_forwarded.unr
  %35 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %.unr
  store i64 %34, ptr %35, align 8, !tbaa !3
  br label %._crit_edge88

._crit_edge88:                                    ; preds = %.peel.next.epil, %._crit_edge88.loopexit.unr-lcssa, %._crit_edge
  %36 = add i64 %14, -3
  %37 = icmp sgt i64 %36, 0
  br i1 %37, label %.lr.ph112, label %._crit_edge88.thread

.lr.ph112:                                        ; preds = %._crit_edge88
  %_QFEans.promoted = load i64, ptr @_QFEans, align 8, !tbaa !3
  %38 = add i64 %14, -1
  %39 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %38
  %40 = load i64, ptr %39, align 8, !tbaa !3
  br label %41

41:                                               ; preds = %.lr.ph112, %.outer._crit_edge
  %.070109 = phi i64 [ 2, %.lr.ph112 ], [ %71, %.outer._crit_edge ]
  %.072108 = phi i64 [ undef, %.lr.ph112 ], [ %.4, %.outer._crit_edge ]
  %42 = phi i64 [ %_QFEans.promoted, %.lr.ph112 ], [ %128, %.outer._crit_edge ]
  %43 = add i64 %.070109, -1
  %44 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %43
  %45 = load i64, ptr %44, align 8, !tbaa !3
  %46 = sitofp i64 %45 to float
  %47 = fmul contract float %46, 5.000000e-01
  %48 = fpext float %47 to double
  %.not8994 = icmp slt i64 %43, 1
  br i1 %.not8994, label %..outer80._crit_edge_crit_edge, label %.lr.ph91

..outer80._crit_edge_crit_edge:                   ; preds = %41
  %.pre = add i64 %.072108, -1
  %.phi.trans.insert = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %.pre
  %.pre126 = load i64, ptr %.phi.trans.insert, align 8, !tbaa !3
  %.pre131 = sitofp i64 %.pre126 to double
  br label %.outer80._crit_edge

.lr.ph91:                                         ; preds = %41, %.outer80
  %.071.ph96 = phi i64 [ %.07190, %.outer80 ], [ %43, %41 ]
  %.074.ph95 = phi i64 [ %58, %.outer80 ], [ 1, %41 ]
  br label %50

49:                                               ; preds = %50
  %.not.not = icmp slt i64 %.074.ph95, %52
  br i1 %.not.not, label %50, label %.outer80._crit_edge

50:                                               ; preds = %.lr.ph91, %49
  %.07190 = phi i64 [ %.071.ph96, %.lr.ph91 ], [ %53, %49 ]
  %51 = add i64 %.07190, %.074.ph95
  %52 = sdiv i64 %51, 2
  %53 = add nsw i64 %52, -1
  %54 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %53
  %55 = load i64, ptr %54, align 8, !tbaa !3
  %56 = sitofp i64 %55 to double
  %57 = fcmp ogt double %56, %48
  br i1 %57, label %49, label %.outer80

.outer80:                                         ; preds = %50
  %58 = add nsw i64 %52, 1
  %.not89.not = icmp slt i64 %52, %.07190
  br i1 %.not89.not, label %.lr.ph91, label %.outer80._crit_edge

.outer80._crit_edge:                              ; preds = %.outer80, %49, %..outer80._crit_edge_crit_edge
  %.pre-phi132 = phi double [ %.pre131, %..outer80._crit_edge_crit_edge ], [ %56, %49 ], [ %56, %.outer80 ]
  %.pre-phi = phi i64 [ %.pre, %..outer80._crit_edge_crit_edge ], [ %53, %49 ], [ %53, %.outer80 ]
  %.173.lcssa = phi i64 [ %.072108, %..outer80._crit_edge_crit_edge ], [ %52, %49 ], [ %52, %.outer80 ]
  %59 = fcmp ogt double %.pre-phi132, %48
  %.2 = select i1 %59, i64 %.pre-phi, i64 %.173.lcssa
  %60 = call i64 @llvm.smax.i64(i64 %.2, i64 1)
  %61 = add nsw i64 %60, -1
  %62 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %61
  %63 = load i64, ptr %62, align 8, !tbaa !3
  %64 = sub i64 %45, %63
  %65 = add i64 %.2, 1
  %66 = call i64 @llvm.smin.i64(i64 %65, i64 %43)
  %67 = add i64 %66, -1
  %68 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %67
  %69 = load i64, ptr %68, align 8, !tbaa !3
  %70 = sub i64 %45, %69
  %71 = add nuw i64 %.070109, 1
  %72 = sub i64 %40, %45
  %73 = sitofp i64 %72 to float
  %74 = fmul contract float %73, 5.000000e-01
  %75 = fpext float %74 to double
  %.not7998104 = icmp sgt i64 %71, %38
  br i1 %.not7998104, label %.outer80._crit_edge..outer._crit_edge_crit_edge, label %.lr.ph100

.outer80._crit_edge..outer._crit_edge_crit_edge:  ; preds = %.outer80._crit_edge
  %.pre127 = add i64 %.2, -1
  %.phi.trans.insert129 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %.pre127
  %.pre130 = load i64, ptr %.phi.trans.insert129, align 8, !tbaa !3
  %.pre133 = sub i64 %.pre130, %45
  %.pre135 = sitofp i64 %.pre133 to double
  br label %.outer._crit_edge

.lr.ph100:                                        ; preds = %.outer80._crit_edge, %.outer
  %.1.ph106 = phi i64 [ %.199, %.outer ], [ %38, %.outer80._crit_edge ]
  %.175.ph105 = phi i64 [ %86, %.outer ], [ %71, %.outer80._crit_edge ]
  br label %77

76:                                               ; preds = %77
  %.not79.not = icmp slt i64 %.175.ph105, %79
  br i1 %.not79.not, label %77, label %.outer._crit_edge

77:                                               ; preds = %.lr.ph100, %76
  %.199 = phi i64 [ %.1.ph106, %.lr.ph100 ], [ %80, %76 ]
  %78 = add i64 %.199, %.175.ph105
  %79 = sdiv i64 %78, 2
  %80 = add nsw i64 %79, -1
  %81 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %80
  %82 = load i64, ptr %81, align 8, !tbaa !3
  %83 = sub i64 %82, %45
  %84 = sitofp i64 %83 to double
  %85 = fcmp ogt double %84, %75
  br i1 %85, label %76, label %.outer

.outer:                                           ; preds = %77
  %86 = add nsw i64 %79, 1
  %.not7998.not = icmp slt i64 %79, %.199
  br i1 %.not7998.not, label %.lr.ph100, label %.outer._crit_edge

.outer._crit_edge:                                ; preds = %.outer, %76, %.outer80._crit_edge..outer._crit_edge_crit_edge
  %.pre-phi136 = phi double [ %.pre135, %.outer80._crit_edge..outer._crit_edge_crit_edge ], [ %84, %76 ], [ %84, %.outer ]
  %.pre-phi128 = phi i64 [ %.pre127, %.outer80._crit_edge..outer._crit_edge_crit_edge ], [ %80, %76 ], [ %80, %.outer ]
  %.3.lcssa = phi i64 [ %.2, %.outer80._crit_edge..outer._crit_edge_crit_edge ], [ %79, %76 ], [ %79, %.outer ]
  %87 = fcmp ogt double %.pre-phi136, %75
  %.4 = select i1 %87, i64 %.pre-phi128, i64 %.3.lcssa
  %88 = call i64 @llvm.smax.i64(i64 %.4, i64 %71)
  %89 = add i64 %88, -1
  %90 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %89
  %91 = load i64, ptr %90, align 8, !tbaa !3
  %92 = sub i64 %91, %45
  %93 = sub i64 %72, %92
  %94 = add i64 %.4, 1
  %95 = call i64 @llvm.smin.i64(i64 %94, i64 %38)
  %96 = add i64 %95, -1
  %97 = getelementptr [200000 x i64], ptr @_QFEs, i64 0, i64 %96
  %98 = load i64, ptr %97, align 8, !tbaa !3
  %99 = sub i64 %98, %45
  %100 = sub i64 %72, %99
  %101 = call i64 @llvm.smax.i64(i64 %63, i64 %64)
  %102 = call i64 @llvm.smax.i64(i64 %101, i64 %92)
  %103 = call i64 @llvm.smax.i64(i64 %102, i64 %93)
  %104 = call i64 @llvm.smin.i64(i64 %63, i64 %64)
  %105 = call i64 @llvm.smin.i64(i64 %104, i64 %92)
  %106 = call i64 @llvm.smin.i64(i64 %105, i64 %93)
  %107 = sub i64 %103, %106
  %108 = call i64 @llvm.smax.i64(i64 %69, i64 %70)
  %109 = call i64 @llvm.smax.i64(i64 %108, i64 %99)
  %110 = call i64 @llvm.smax.i64(i64 %109, i64 %100)
  %111 = call i64 @llvm.smin.i64(i64 %69, i64 %70)
  %112 = call i64 @llvm.smin.i64(i64 %111, i64 %99)
  %113 = call i64 @llvm.smin.i64(i64 %112, i64 %100)
  %114 = sub i64 %110, %113
  %115 = call i64 @llvm.smax.i64(i64 %101, i64 %99)
  %116 = call i64 @llvm.smax.i64(i64 %115, i64 %100)
  %117 = call i64 @llvm.smin.i64(i64 %104, i64 %99)
  %118 = call i64 @llvm.smin.i64(i64 %117, i64 %100)
  %119 = sub i64 %116, %118
  %120 = call i64 @llvm.smax.i64(i64 %108, i64 %92)
  %121 = call i64 @llvm.smax.i64(i64 %120, i64 %93)
  %122 = call i64 @llvm.smin.i64(i64 %111, i64 %92)
  %123 = call i64 @llvm.smin.i64(i64 %122, i64 %93)
  %124 = sub i64 %121, %123
  %125 = call i64 @llvm.smin.i64(i64 %42, i64 %107)
  %126 = call i64 @llvm.smin.i64(i64 %125, i64 %114)
  %127 = call i64 @llvm.smin.i64(i64 %126, i64 %119)
  %128 = call i64 @llvm.smin.i64(i64 %127, i64 %124)
  %exitcond125.not = icmp eq i64 %71, %38
  br i1 %exitcond125.not, label %._crit_edge113, label %41

._crit_edge113:                                   ; preds = %.outer._crit_edge
  store i64 %128, ptr @_QFEans, align 8, !tbaa !3
  br label %._crit_edge88.thread

._crit_edge88.thread:                             ; preds = %16, %._crit_edge113, %._crit_edge88
  %129 = call ptr @_FortranAioBeginExternalListOutput(i32 -1, ptr nonnull @_QQcl.1798884dfd1b212b4237fe99fdbff199, i32 79)
  %130 = load i64, ptr @_QFEans, align 8, !tbaa !3
  %131 = call i1 @_FortranAioOutputInteger64(ptr %129, i64 %130)
  %132 = call i32 @_FortranAioEndIoStatement(ptr %129)
  ret void
}

declare ptr @_FortranAioBeginExternalListInput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioInputInteger(ptr, ptr, i32) local_unnamed_addr

declare i32 @_FortranAioEndIoStatement(ptr) local_unnamed_addr

declare ptr @_FortranAioBeginExternalListOutput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioOutputInteger64(ptr, i64) local_unnamed_addr

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i64 @llvm.smax.i64(i64, i64) #0

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i64 @llvm.smin.i64(i64, i64) #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

!llvm.module.flags = !{!0, !1, !2}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{!4, !4, i64 0}
!4 = !{!"any data access", !5, i64 0}
!5 = !{!"any access", !6, i64 0}
!6 = !{!"Flang Type TBAA Root"}
!7 = distinct !{!7, !8}
!8 = !{!"llvm.loop.peeled.count", i32 1}
