import Foundation





func first(_ secondStr: String, _ thirdStr: String) -> String {
   if secondStr == "0" { return "1"}
   if secondStr == "1" { return "0"}
   
   if thirdStr == "1" { return "1"}
   return "0"
}

func count2(S: [String]) -> Int {
   if S.contains("1") == false && S.contains("0") == false { return 1}
   
   if S.contains("?") == false {
      if Int(S[0])! ^ Int(S[1])! == 0 { return 1 }
      return 2
   }
   return 1
}

struct MaxState {
   var HatenaFlag = false
   var isOne = false
   var isZero = false
   var oneFirst = 0
   var oneEnd = 0
   var zeroFirst = 0
   var zeroEnd = 0
   
   var oneCount = 0
   var zeroCount = 0
   
   var oneMaxFirst = 0
   var oneMaxEnd = 0
   var zeroMaxFirst = 0
   var zeroMaxEnd = 0
   
   var oneMax = 0
   var zeroMax = 0
}


func WhenOne(First: Int, End: Int, MaxArray: Int, S: [String]) -> Int {
   let max = End - First + 1
   
   var currentMax = max
   var maxes = max
   
   var tmp = First - 1
   
   while tmp >= 0 {
      if S[tmp] == "0" || S[tmp] == "?" {
         maxes -= 1
      } else {
         maxes += 1
         if maxes > currentMax {
            currentMax = maxes
         }
      }
      tmp -= 1
   }
   
   tmp = End + 1
   maxes = currentMax
   
   while tmp <= MaxArray {
      if S[tmp] == "0" || S[tmp] == "?" {
         maxes -= 1
      } else {
         maxes += 1
         if maxes > currentMax {
            currentMax = maxes
         }
      }
      tmp += 1
   }
   
   return currentMax
}

func WhenZero(First: Int, End: Int, MaxArray: Int, S: [String]) -> Int {
   let max = End - First + 1
   
   var currentMax = max
   var maxes = max
   
   var tmp = First - 1
   
   while tmp >= 0 {
      if S[tmp] == "1" || S[tmp] == "?" {
         maxes -= 1
      } else {
         maxes += 1
         if maxes > currentMax {
            currentMax = maxes
         }
      }
      tmp -= 1
   }
   
   tmp = End + 1
   maxes = currentMax
   
   while tmp <= MaxArray {
      if S[tmp] == "1" || S[tmp] == "?" {
         maxes -= 1
      } else {
         maxes += 1
         if maxes > currentMax {
            currentMax = maxes
         }
      }
      tmp += 1
   }
   
   return currentMax
}


func B01(S: [String]) -> Int {
   var S = S
   if S.count == 1 { return 1 }
   if S.count == 2 { return count2(S: S) }
   if !S.contains("1") && !S.contains("0") { return 1}
   
   S[0] = first(S[1], S[2])

   var maxState = MaxState()
   
   for tmp in 0 ..< S.count {
      if S[tmp] == "?" && maxState.isOne {
         if maxState.oneCount > maxState.oneMax {
            maxState.oneMaxFirst = maxState.oneFirst
            maxState.oneMaxEnd = tmp - 1
            maxState.oneMax = maxState.oneCount
            maxState.oneFirst = 0
         }
         maxState.isOne = false
         maxState.HatenaFlag = true
         continue
      }
      
      if S[tmp] == "?" && maxState.isZero {
         if maxState.zeroCount > maxState.zeroMax {
            maxState.zeroMaxFirst = maxState.zeroFirst
            maxState.zeroMaxEnd = tmp - 1
            maxState.zeroMax = maxState.zeroCount
            maxState.zeroFirst = 0
         }
         maxState.isZero = false
         maxState.HatenaFlag = true
         continue
      }
      
      if S[tmp] == "?" {
         maxState.HatenaFlag = true
         continue
      }
      
      if S[tmp] == "1" && !maxState.isOne {
         maxState.HatenaFlag = false
         maxState.isOne = true
         maxState.isZero = false
         
         maxState.oneFirst = tmp
         maxState.oneCount = 1
         continue
      }
      
      if S[tmp] == "0" && !maxState.isZero {
         maxState.HatenaFlag = false
         maxState.isOne = false
         maxState.isZero = true
         
         maxState.zeroFirst = tmp
         maxState.zeroCount = 1
         continue
      }
      
      if S[tmp] == "1" && maxState.isOne {
         maxState.oneCount += 1
         continue
      }
      
      if S[tmp] == "0" && maxState.isZero {
         maxState.zeroCount += 1
         continue
      }
      
      if S[tmp] == "0" && maxState.isOne {
         if maxState.oneCount > maxState.oneMax {
            maxState.oneMaxFirst = maxState.oneFirst
            maxState.oneMaxEnd = tmp - 1
            maxState.oneMax = maxState.oneCount
            maxState.oneFirst = 0
         }
         maxState.HatenaFlag = false
         maxState.isOne = false
         maxState.isZero = true
         
         maxState.oneFirst = tmp
         maxState.oneCount = 1
         continue
      }
      
      if S[tmp] == "1" && maxState.isZero {
         if maxState.zeroCount > maxState.zeroMax {
            maxState.zeroMaxFirst = maxState.zeroFirst
            maxState.zeroMaxEnd = tmp - 1
            maxState.zeroMax = maxState.zeroCount
            maxState.zeroFirst = 0
         }
         maxState.HatenaFlag = false
         maxState.isOne = true
         maxState.isZero = false
         
         maxState.zeroFirst = tmp
         maxState.zeroCount = 1
         continue
      }
   }
   
   

   
   let whenOne = WhenOne(First: maxState.oneMaxFirst, End: maxState.oneMaxEnd, MaxArray: S.count - 1, S: S)
   let whenZero = WhenZero(First: maxState.zeroMaxFirst, End: maxState.zeroMaxEnd, MaxArray: S.count - 1, S: S)
   

   
   if whenOne > whenZero {
      return whenOne
   } else {
      return whenZero
   }
}