program ioi_to_oio
  implicit none
  integer :: n, a(500000), x(0:500000), dp(500000), i, j, k, d
  character(500000) :: s
  a = 0
  x = 0
  dp = 0
  read(*,*) n
  read(*,*) s
  do i = 1, n
    if (s(i:i).eq."1") then
      a(i) = 1
      x(i) = x(i-1)+1
    end if
  end do
  do i = 3, n
    dp(i) = dp(i-1)
    if (a(i).eq.0) cycle
    if (a(i-2)-a(i-1).eq.1) then
      do d = 0, 2
        if (x(i-2).le.d) exit
        j = i-2-(x(i-2)-d)
        k = 0
        if (j.ge.1) k = dp(j)
        dp(i) = max(dp(i),x(i-2)-d+k)
      end do
    end if
    if (i-x(i)-1.ge.1.and.a(i-x(i)-1).eq.1) then
      j = i-2-x(i)
      k = 0
      if (j.ge.1) k = dp(j)
      dp(i) = max(dp(i),x(i)+k)
    end if
  end do
  write(*,'(i0)') dp(n)
  stop
end program ioi_to_oio
; 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 unnamed_addr global [500000 x i32] undef
@_QFEdp = internal unnamed_addr global [500000 x i32] undef
@_QFEs = internal global [500000 x i8] undef
@_QFEx = internal unnamed_addr global [500001 x i32] undef
@_QQcl.72acacfa1ee66dea53e3d41e1739fa4a = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_6849/source.f\00"
@_QQcl.31 = linkonce constant [1 x i8] c"1"
@_QQcl.28693029 = linkonce constant [4 x i8] c"(i0)"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

; Function Attrs: noreturn
define void @_QQmain() local_unnamed_addr #0 {
.preheader41.preheader:
  %0 = alloca i32, align 4
  tail call void @llvm.memset.p0.i64(ptr noundef nonnull align 16 dereferenceable(2000000) @_QFEa, i8 0, i64 2000000, i1 false), !tbaa !3
  tail call void @llvm.memset.p0.i64(ptr noundef nonnull align 16 dereferenceable(2000004) @_QFEx, i8 0, i64 2000004, i1 false), !tbaa !3
  tail call void @llvm.memset.p0.i64(ptr noundef nonnull align 16 dereferenceable(2000000) @_QFEdp, i8 0, i64 2000000, i1 false), !tbaa !3
  %1 = tail call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.72acacfa1ee66dea53e3d41e1739fa4a, i32 8)
  %2 = call i1 @_FortranAioInputInteger(ptr %1, ptr nonnull %0, i32 4)
  %3 = call i32 @_FortranAioEndIoStatement(ptr %1)
  %4 = call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.72acacfa1ee66dea53e3d41e1739fa4a, i32 9)
  %5 = call i1 @_FortranAioInputAscii(ptr %4, ptr nonnull @_QFEs, i64 500000)
  %6 = call i32 @_FortranAioEndIoStatement(ptr %4)
  %7 = load i32, ptr %0, align 4, !tbaa !3
  %8 = icmp sgt i32 %7, 0
  br i1 %8, label %.lr.ph.preheader, label %._crit_edge

.lr.ph.preheader:                                 ; preds = %.preheader41.preheader
  %9 = zext i32 %7 to i64
  br label %.lr.ph

.lr.ph:                                           ; preds = %.lr.ph.preheader, %20
  %indvars.iv = phi i64 [ 1, %.lr.ph.preheader ], [ %indvars.iv.next, %20 ]
  %10 = add nsw i64 %indvars.iv, -1
  %11 = getelementptr [500000 x [1 x i8]], ptr @_QFEs, i64 0, i64 %10
  %12 = call i32 @_FortranACharacterCompareScalar1(ptr %11, ptr nonnull @_QQcl.31, i64 1, i64 1)
  %13 = icmp eq i32 %12, 0
  br i1 %13, label %14, label %20

14:                                               ; preds = %.lr.ph
  %15 = getelementptr [500000 x i32], ptr @_QFEa, i64 0, i64 %10
  store i32 1, ptr %15, align 4, !tbaa !3
  %16 = getelementptr [500001 x i32], ptr @_QFEx, i64 0, i64 %10
  %17 = load i32, ptr %16, align 4, !tbaa !3
  %18 = add i32 %17, 1
  %19 = getelementptr [500001 x i32], ptr @_QFEx, i64 0, i64 %indvars.iv
  store i32 %18, ptr %19, align 4, !tbaa !3
  br label %20

20:                                               ; preds = %14, %.lr.ph
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv, %9
  br i1 %exitcond.not, label %._crit_edge.loopexit, label %.lr.ph

._crit_edge.loopexit:                             ; preds = %20
  %.pre = load i32, ptr %0, align 4, !tbaa !3
  br label %._crit_edge

._crit_edge:                                      ; preds = %._crit_edge.loopexit, %.preheader41.preheader
  %21 = phi i32 [ %.pre, %._crit_edge.loopexit ], [ %7, %.preheader41.preheader ]
  %22 = add i32 %21, -2
  %23 = icmp sgt i32 %22, 0
  br i1 %23, label %.lr.ph47.preheader, label %._crit_edge48

.lr.ph47.preheader:                               ; preds = %._crit_edge
  %.pre56 = load i32, ptr getelementptr inbounds ([500000 x i32], ptr @_QFEdp, i64 0, i64 1), align 4, !tbaa !3
  br label %.lr.ph47

.lr.ph47:                                         ; preds = %.lr.ph47.preheader, %104
  %24 = phi i32 [ %105, %104 ], [ %.pre56, %.lr.ph47.preheader ]
  %.02845 = phi i32 [ %106, %104 ], [ 3, %.lr.ph47.preheader ]
  %25 = sext i32 %.02845 to i64
  %26 = add nsw i64 %25, -1
  %27 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %26
  store i32 %24, ptr %27, align 4, !tbaa !3
  %28 = getelementptr [500000 x i32], ptr @_QFEa, i64 0, i64 %26
  %29 = load i32, ptr %28, align 4, !tbaa !3
  %.not = icmp eq i32 %29, 0
  br i1 %.not, label %104, label %30

30:                                               ; preds = %.lr.ph47
  %31 = add i32 %.02845, -1
  %32 = sext i32 %31 to i64
  %33 = add nsw i64 %32, -1
  %34 = add i32 %.02845, -2
  %35 = sext i32 %34 to i64
  %36 = add nsw i64 %35, -1
  %37 = getelementptr [500000 x i32], ptr @_QFEa, i64 0, i64 %36
  %38 = load i32, ptr %37, align 4, !tbaa !3
  %39 = getelementptr [500000 x i32], ptr @_QFEa, i64 0, i64 %33
  %40 = load i32, ptr %39, align 4, !tbaa !3
  %41 = sub i32 %38, %40
  %42 = icmp eq i32 %41, 1
  br i1 %42, label %.preheader, label %.loopexit

.preheader:                                       ; preds = %30
  %43 = getelementptr [500001 x i32], ptr @_QFEx, i64 0, i64 %35
  %44 = load i32, ptr %43, align 4, !tbaa !3
  %smax = call i32 @llvm.smax.i32(i32 %44, i32 0)
  %exitcond53.not = icmp slt i32 %44, 1
  br i1 %exitcond53.not, label %.loopexit, label %45

45:                                               ; preds = %.preheader
  %46 = sub i32 %34, %44
  %47 = icmp sgt i32 %46, 0
  br i1 %47, label %48, label %53

48:                                               ; preds = %45
  %49 = zext i32 %46 to i64
  %50 = add nsw i64 %49, -1
  %51 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %50
  %52 = load i32, ptr %51, align 4, !tbaa !3
  br label %53

53:                                               ; preds = %48, %45
  %.0 = phi i32 [ %52, %48 ], [ 0, %45 ]
  %54 = add i32 %44, %.0
  %55 = call i32 @llvm.smax.i32(i32 %24, i32 %54)
  store i32 %55, ptr %27, align 4, !tbaa !3
  %exitcond53.1.not = icmp eq i32 %smax, 1
  br i1 %exitcond53.1.not, label %.loopexit, label %56

56:                                               ; preds = %53
  %57 = xor i32 %44, -1
  %58 = add i32 %.02845, %57
  %59 = icmp sgt i32 %58, 0
  br i1 %59, label %60, label %65

60:                                               ; preds = %56
  %61 = zext i32 %58 to i64
  %62 = add nsw i64 %61, -1
  %63 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %62
  %64 = load i32, ptr %63, align 4, !tbaa !3
  br label %65

65:                                               ; preds = %60, %56
  %.0.1 = phi i32 [ %64, %60 ], [ 0, %56 ]
  %66 = add nsw i32 %44, -1
  %67 = add i32 %66, %.0.1
  %68 = call i32 @llvm.smax.i32(i32 %55, i32 %67)
  store i32 %68, ptr %27, align 4, !tbaa !3
  %exitcond53.2.not = icmp eq i32 %smax, 2
  br i1 %exitcond53.2.not, label %.loopexit, label %69

69:                                               ; preds = %65
  %70 = sub i32 %.02845, %44
  %71 = icmp sgt i32 %70, 0
  br i1 %71, label %72, label %77

72:                                               ; preds = %69
  %73 = zext i32 %70 to i64
  %74 = add nsw i64 %73, -1
  %75 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %74
  %76 = load i32, ptr %75, align 4, !tbaa !3
  br label %77

77:                                               ; preds = %72, %69
  %.0.2 = phi i32 [ %76, %72 ], [ 0, %69 ]
  %78 = add nsw i32 %44, -2
  %79 = add i32 %78, %.0.2
  %80 = call i32 @llvm.smax.i32(i32 %68, i32 %79)
  store i32 %80, ptr %27, align 4, !tbaa !3
  br label %.loopexit

.loopexit:                                        ; preds = %.preheader, %53, %65, %77, %30
  %81 = phi i32 [ %24, %30 ], [ %80, %77 ], [ %68, %65 ], [ %55, %53 ], [ %24, %.preheader ]
  %82 = getelementptr [500001 x i32], ptr @_QFEx, i64 0, i64 %25
  %83 = load i32, ptr %82, align 4, !tbaa !3
  %84 = xor i32 %83, -1
  %85 = add i32 %.02845, %84
  %86 = icmp sgt i32 %85, 0
  %87 = sext i32 %85 to i64
  %88 = add nsw i64 %87, -1
  %89 = getelementptr [500000 x i32], ptr @_QFEa, i64 0, i64 %88
  %90 = load i32, ptr %89, align 4, !tbaa !3
  %91 = icmp eq i32 %90, 1
  %92 = and i1 %86, %91
  br i1 %92, label %93, label %104

93:                                               ; preds = %.loopexit
  %94 = sub i32 %34, %83
  %95 = icmp sgt i32 %94, 0
  br i1 %95, label %96, label %101

96:                                               ; preds = %93
  %97 = zext i32 %94 to i64
  %98 = add nsw i64 %97, -1
  %99 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %98
  %100 = load i32, ptr %99, align 4, !tbaa !3
  br label %101

101:                                              ; preds = %96, %93
  %.1 = phi i32 [ %100, %96 ], [ 0, %93 ]
  %102 = add i32 %.1, %83
  %103 = call i32 @llvm.smax.i32(i32 %81, i32 %102)
  store i32 %103, ptr %27, align 4, !tbaa !3
  br label %104

104:                                              ; preds = %101, %.loopexit, %.lr.ph47
  %105 = phi i32 [ %103, %101 ], [ %81, %.loopexit ], [ %24, %.lr.ph47 ]
  %106 = add nuw i32 %.02845, 1
  %exitcond55.not = icmp eq i32 %.02845, %21
  br i1 %exitcond55.not, label %._crit_edge48, label %.lr.ph47

._crit_edge48:                                    ; preds = %104, %._crit_edge
  %107 = call ptr @_FortranAioBeginExternalFormattedOutput(ptr nonnull @_QQcl.28693029, i64 4, ptr null, i32 -1, ptr nonnull @_QQcl.72acacfa1ee66dea53e3d41e1739fa4a, i32 35)
  %108 = load i32, ptr %0, align 4, !tbaa !3
  %109 = sext i32 %108 to i64
  %110 = add nsw i64 %109, -1
  %111 = getelementptr [500000 x i32], ptr @_QFEdp, i64 0, i64 %110
  %112 = load i32, ptr %111, align 4, !tbaa !3
  %113 = call i1 @_FortranAioOutputInteger32(ptr %107, i32 %112)
  %114 = call i32 @_FortranAioEndIoStatement(ptr %107)
  %115 = call {} @_FortranAStopStatement(i32 0, i1 false, i1 false)
  unreachable
}

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 i1 @_FortranAioInputAscii(ptr, ptr, i64) local_unnamed_addr

declare i32 @_FortranACharacterCompareScalar1(ptr, ptr, i64, i64) local_unnamed_addr

declare ptr @_FortranAioBeginExternalFormattedOutput(ptr, i64, ptr, i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioOutputInteger32(ptr, i32) local_unnamed_addr

declare {} @_FortranAStopStatement(i32, i1, i1) local_unnamed_addr

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

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #2

attributes #0 = { noreturn }
attributes #1 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #2 = { nocallback nofree nounwind willreturn memory(argmem: write) }

!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"}
