You are given a binary string S. You are allowed to perform the following operation at most once:
Pick some [substring] of S
Flip all the values in this substring, i.e, convert 0 to 1 and vice versa

For example, if S = 1\underline{00101}011, you can pick the underlined substring and flip it to obtain S = 1\underline{11010}011.

For the substring of S consisting of all the positions from L to R, we define a function f(L, R) to be the number of 1's in this substring. For example, if S = 100101011, then f(2, 5) = 1 and f(4, 9) = 4 (the respective substrings are 0010 and 101011).

If you perform the given operation optimally, find the maximum possible value of

\sum_{L=1}^N \sum_{R=L}^N f(L, R)

that can be obtained. Note that the substring flip operation can be performed at most once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single line of input, containing a binary string S.

------ Output Format ------ 

For each test case, output on a new line the maximum possible value of \sum_{L=1}^N \sum_{R=L}^N f(L, R) that can be obtained.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 3\cdot 10^{5}$
- The sum of $|S|$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
111
000
00100
----- Sample Output 1 ------ 
10
10
26
----- explanation 1 ------ 
Test case $1$: There is no need to apply the operation since everything is already a $1$. The answer is thus the sum of:
- $f(1, 1) = 1$
- $f(1, 2) = 2$
- $f(1, 3) = 3$
- $f(2, 2) = 1$
- $f(2, 3) = 2$
- $f(3, 3) = 1$

which is $10$.

Test case $2$: Flip the entire string to obtain $111$, whose answer has been computed above.

Test case $3$: Flip the entire string to obtain $11011$. The sum of $f(L, R)$ across all substrings is now $26$, which is the maximum possible.

Difficulty: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	s = input()
	a = 0
	b = 0
	c = 0
	for j in range(len(s)):
		x = (j + 1) * (len(s) - j)
		if s[j] == '1':
			a += x
			x = x * -1
		b += x
		b = max(b, 0)
		c = max(b, c)
	print(c + a)


for tea in range(int(input())):
	s = [int(qwera) for qwera in list(input())]
	n = len(s)
	values = []
	for i in range(n):
		if s[i] == 1:
			values.append(-(i + 1) * (n - i))
		else:
			values.append((i + 1) * (n - i))
	curr = sum([-values[i] if s[i] == 1 else 0 for i in range(n)])
	pfs = [0]
	for j in values:
		pfs.append(pfs[-1] + j)
	mini = 0
	best = 0
	for k in range(1, n + 1):
		best = max(best, pfs[k] - mini)
		mini = min(pfs[k], mini)
	print(best + curr)


def maxSubarraySum(l):
	localMax = globalMax = l[0]
	for i in range(1, len(l)):
		localMax = max(l[i], localMax + l[i])
		if localMax > globalMax:
			globalMax = localMax
	return globalMax
for _ in range(int(input())):
	s = input()
	l = []
	initialSum = 0
	n = len(s)
	for i in range(n):
		f = (i + 1) * (n - i)
		if s[i] == '1':
			initialSum += f
			l.append(-f)
		else:
			l.append(f)
	m = maxSubarraySum(l)
	if m > 0:
		initialSum += m
	print(initialSum)


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	res = ans = m = 0
	for i in range(l):
		v = (i + 1) * (l - i)
		if s[i] == '1':
			ans += v
			v = v * -1
		m += v
		m = max(m, 0)
		res = max(m, res)
	print(res + ans)


from collections import Counter, defaultdict
import sys
import math

def sol(n, s):
	wt = [0] * n
	for i in range(n):
		if i == 0 or i == n - 1:
			wt[i] = n
		else:
			wt[i] = (i + 1) * (n - i)
	max_end_here = 0
	max_so_far = 0
	c_sum = 0
	for i in range(n):
		if s[i] == '1':
			c_sum += wt[i]
			max_end_here -= wt[i]
		else:
			max_end_here += wt[i]
		if max_end_here < 0:
			max_end_here = 0
		max_so_far = max(max_so_far, max_end_here)
	return c_sum + max_so_far
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	s = insr()
	x = []
	for i in range(len(s)):
		if s[i] == '1' or s[i] == '0':
			x.append(s[i])
	s = x
	n = len(s)
	print(sol(n, s))


for _ in range(int(input())):
	s = input()
	n = len(s)
	res = maxi = ans = 0
	for i in range(n):
		sub = (i + 1) * (n - i)
		if s[i] == '1':
			ans += sub
			sub = sub * -1
		res += sub
		res = max(res, 0)
		maxi = max(maxi, res)
	print(maxi + ans)


for _ in range(int(input())):
	s = input()
	ans = mx = cur = 0
	for i in range(len(s)):
		subarrays = (i + 1) * (len(s) - i)
		if s[i] == '1':
			ans += subarrays
			subarrays *= -1
		cur += subarrays
		cur = max(cur, 0)
		mx = max(mx, cur)
	print(ans + mx)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
for _ in range(ni()):
	s = input()
	ans = mx = cur = 0
	for i in range(len(s)):
		subarrays = (i + 1) * (len(s) - i)
		if s[i] == '1':
			ans += subarrays
			subarrays *= -1
		cur += subarrays
		cur = max(cur, 0)
		mx = max(mx, cur)
	print(ans + mx)


t = int(input())
for _ in range(t):
	s = input()
	cm_array = []
	cm = 0
	pv = s[0]
	n = len(s)
	tot = 0
	for i in range(n):
		v = s[i]
		if v == '1':
			tot += (i + 1) * (n - i)
		if v == pv:
			cm += (i + 1) * (n - i)
		else:
			if pv == '1':
				cm = -cm
			cm_array.append(cm)
			pv = v
			cm = (i + 1) * (n - i)
	if pv == '1':
		cm = -cm
	cm_array.append(cm)
	o_max = 0
	ct = 0
	for v in cm_array:
		ct += v
		if ct > o_max:
			o_max = ct
		if ct <= 0:
			ct = 0
	ans = tot + o_max
	print(ans)


t = int(input())
for _ in range(t):
	s = list(map(int, list(input())))
	n = len(s)
	a = [0] * n
	c = 0
	for i in range(n + 1 >> 1):
		j = (i + 1) * (n - i)
		c += j * s[i]
		m = -1 if s[i] else 1
		a[i] = m * j
		if i != n - i - 1:
			c += j * s[n - i - 1]
			m = -1 if s[n - i - 1] else 1
			a[n - i - 1] = m * j
	p = 0
	q = 0
	for x in a:
		p = max(0, p + x)
		q = max(q, p)
	print(c + q)


for _ in range(int(input())):
	S = input()
	ln = len(S)
	tot = 0
	mult = [0] * ln
	for i in range(ln):
		t = (i + 1) * (ln - i)
		mult[i] = t
		if S[i] == '1':
			tot += t
			mult[i] = -t
	maxSoFar = -999999999999999
	maxEndingHere = 0
	for i in range(t):
		maxEndingHere += mult[i]
		if maxEndingHere > maxSoFar:
			maxSoFar = maxEndingHere
		if maxEndingHere < 0:
			maxEndingHere = 0
	if maxSoFar < 0:
		maxSoFar = 0
	print(tot + maxSoFar)


for _ in range(int(input())):
	S = input()
	N = len(S)
	res = cur = mx = 0
	for i in range(N):
		v = (i + 1) * (N - i)
		if S[i] == '1':
			res += v
			v *= -1
		cur += v
		cur = max(cur, 0)
		mx = max(mx, cur)
	print(mx + res)


def kadanes(a, size):
	max_so_far = -float('inf')
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	return (max_so_far, start, end)
for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	for i in range(n):
		if s[i] == '1':
			ans += (i + 1) * (n - i)
	arr = []
	for i in range(n):
		if s[i] == '1':
			arr.append(-((i + 1) * (n - i)))
		else:
			arr.append((i + 1) * (n - i))
	(maxx, start, end) = kadanes(arr, len(arr))
	print(ans + max(0, maxx))


for _ in range(int(input())):
	s = input()
	n = len(s)
	arr = []
	(prev, ind) = (0, 0)
	bow = []
	for i in range(n):
		front = prev
		bow.append(int(s[i]) * (i + 1) * (n - i))
		if s[i] == '1':
			prev -= (i + 1) * (n - i)
		else:
			prev += (i + 1) * (n - i)
		prev = max(prev, 0)
		if prev == 0 or front == 0:
			ind = i
		arr.append([prev, ind, i])
	(maxy, start, end) = max(arr, key=lambda x: x[0])
	print(sum(bow) + maxy)


test = int(input())
while test:
	s = input()
	n = len(s)
	contribution = []
	original_score = 0
	for i in range(n):
		contribution.append((i + 1) * (n - i))
		if s[i] == '1':
			original_score += contribution[i]
			contribution[i] *= -1
	maxi = curr_sum = 0
	for i in contribution:
		curr_sum += i
		if curr_sum < 0:
			curr_sum = 0
		maxi = max(curr_sum, maxi)
	if maxi > 0:
		print(original_score + maxi)
	else:
		print(original_score)
	test -= 1


from sys import stdin
input = stdin.readline

def kadane(A):
	max_so_far = 0
	curr_max = 0
	N = len(A)
	for i in range(N):
		curr_max += A[i]
		if curr_max < 0:
			curr_max = 0
		elif max_so_far < curr_max:
			max_so_far = curr_max
	return max_so_far

def solve(S):
	N = len(S)
	S = [int(s) for s in S]
	total = sum((S[i] * (i + 1) * (N - i) for i in range(N)))
	flip = [(1 - 2 * S[i]) * (i + 1) * (N - i) for i in range(N)]
	return total + kadane(flip)
T = int(input().strip())
for problem in range(1, T + 1):
	S = input().strip()
	print(solve(S))


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	res = 0
	lst = []
	for i in range(n):
		if s[i] == '0':
			lst.append((i + 1) * (n - i))
		else:
			lst.append(-(i + 1) * (n - i))
			res += (i + 1) * (n - i)
	d = 0
	cur = 0
	for i in range(n):
		cur += lst[i]
		if cur <= 0:
			cur = 0
		else:
			d = max(d, cur)
	print(res + d)


def I():
	return input()

def II():
	return int(input())

def solve():
	s = I()
	n = len(s)
	res = 0
	lst = []
	for i in range(n):
		if s[i] == '0':
			lst.append((i + 1) * (n - i))
		else:
			lst.append(-(i + 1) * (n - i))
			res += (i + 1) * (n - i)
	d = 0
	cur = 0
	for i in range(n):
		cur += lst[i]
		if cur <= 0:
			cur = 0
		else:
			d = max(d, cur)
	print(res + d)
for _ in range(II()):
	solve()


maxint = 100000000000

def maxSubArraySum(a, size):
	max_so_far = -maxint - 1
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
for t in range(int(input())):
	s = str(input())
	a = []
	n = len(s)
	if n % 2 == 0:
		a.append(n)
		for i in range(n - 2, 1, -2):
			a.append(a[-1] + i)
		a += reversed(a)
	else:
		a.append(n)
		for i in range(n - 2, 0, -2):
			a.append(a[-1] + i)
		a += reversed(a)
		a.pop(len(a) // 2)
	total = 0
	for i in range(n):
		if s[i] == '1':
			total += a[i]
			a[i] = -a[i]
	print(total + max(0, maxSubArraySum(a, n)))


t = int(input())
for i in range(t):
	s = list(input())
	n = len(s)
	score = 0
	for j in range(n):
		if s[j] == '1':
			score = score + (j + 1) * (n - j)
	maxscorediff = 0
	max_ending_here = 0
	for j in range(n):
		diff = (j + 1) * (n - j)
		if s[j] == '1':
			diff = -diff
		max_ending_here = max_ending_here + diff
		if maxscorediff < max_ending_here:
			maxscorediff = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	print(score + maxscorediff)


from collections import defaultdict
n = int(input())
for i in range(n):
	p = input()
	l = []

	def maxSubArraySum(a, size):
		max_so_far = -float('inf')
		max_ending_here = 0
		start = 0
		end = 0
		s = 0
		for i in range(0, size):
			if a[i] == '1':
				max_ending_here -= (i + 1) * (len(a) - i)
			else:
				max_ending_here += (i + 1) * (len(a) - i)
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
				start = s
				end = i
			if max_ending_here < 0:
				max_ending_here = 0
				s = i + 1
		return (max_so_far, start, end)
	(c, a, b) = maxSubArraySum(p, len(p))
	l = []
	if a == b and p[a] == '1' and (a == 0):
		l = list(p)
		ans = 0
		for i in range(len(l)):
			if l[i] == '1':
				ans += (i + 1) * (len(p) - i)
		print(ans)
	else:
		for i in range(len(p)):
			if a <= i <= b:
				if p[i] == '1':
					l.append('0')
					c += (i + 1) * (len(p) - i)
				else:
					l.append('1')
			else:
				l.append(p[i])
				if p[i] == '1':
					c += (i + 1) * (len(p) - i)
		print(c)


t = int(input())

def getctr(n):
	res = [0] * n
	i = 0
	j = n - 1
	v = n
	while i <= j:
		if i > 0:
			res[i] = res[i - 1] + v
			res[j] = res[j + 1] + v
		else:
			res[i] = n
			res[j] = n
		i += 1
		j -= 1
		v -= 2
	return res
for _ in range(t):
	s = list(map(int, input()))
	n = len(s)
	ctr = getctr(n)
	p = [0]
	pall = [0]
	for i in range(n):
		p.append(p[-1] + ctr[i] * s[i])
		pall.append(pall[-1] + ctr[i])
	newp = [pall[i] - 2 * p[i] for i in range(n + 1)]
	res = p[-1]
	minyet = float('inf')
	for el in newp:
		minyet = min(minyet, el)
		res = max(res, el - minyet + p[-1])
	print(res)


iter = int(input())
for z in range(iter):
	s = input()
	n = len(s)
	score = [0] * n
	c = 0
	m = 0
	neg = 0
	ans = 0
	for i in range(len(s)):
		score[i] = (i + 1) * (n - i)
		if s[i] == '1':
			ans += score[i]
			score[i] = -score[i]
	for i in range(n):
		c += score[i]
		if score[i] < 0:
			neg += score[i]
		if c <= 0:
			c = 0
			neg = 0
		m = max(m, c)
	print(ans + m)


T = int(input())
for t in range(T):
	S = [int(x) for x in input()]
	N = len(S)
	G = [i * (N - i + 1) for i in range(1, N + 1)]
	G_nop = [G[i - 1] if S[i - 1] == 1 else 0 for i in range(1, N + 1)]
	s = sum(G_nop)
	max_diff = 0
	cur_diff = 0
	for i in range(N):
		if S[i] == 0:
			cur_diff += G[i]
			max_diff = max(max_diff, cur_diff)
		else:
			cur_diff -= G[i]
			cur_diff = max(cur_diff, 0)
	print(s + max_diff)


for _ in range(int(input())):
	s = input()
	con = []
	ans = 0
	for i in range(len(s)):
		con.append((i + 1) * (len(s) - i))
		if s[i] == '1':
			ans += con[i]
			con[i] *= -1
	maxi = 0
	curr = 0
	for i in range(len(con)):
		curr += con[i]
		if curr < 0:
			curr = 0
		maxi = max(maxi, curr)
	print(ans + maxi)


for _ in range(int(input())):
	s = input()
	n = len(s)
	arr = [0] * (n + 1)
	bla = 0
	for i in range(1, n + 1):
		if s[i - 1] == '1':
			arr[i] = -1 * i * (n - i + 1)
			bla += i * (n - i + 1)
		else:
			arr[i] = i * (n - i + 1)
	fin_ans = 0
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		x = s[i - 1]
		dp[i] = max(dp[i - 1] + arr[i], arr[i])
		fin_ans = max(fin_ans, dp[i])
	print(bla + fin_ans)


import sys
input = sys.stdin.readline
from math import sqrt, ceil, floor
from collections import defaultdict

def I():
	return list(map(int, input().split()))
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	val = [0] * n
	for i in range(n):
		val[i] = (i + 1) * (n - i)
	val_til_now = 0
	max_val = -1
	sub = [-1, -1]
	count = 0
	for i in range(n):
		count += 1
		if s[i] == '1':
			val_til_now -= val[i]
		else:
			val_til_now += val[i]
		if val_til_now <= 0:
			val_til_now = 0
			count = 0
		elif val_til_now > max_val:
			max_val = val_til_now
			sub = [i - count + 1, i]
	l = []
	l[:] = s
	if sub != [-1, -1]:
		for i in range(sub[0], sub[1] + 1):
			if l[i] == '0':
				l[i] = '1'
			else:
				l[i] = '0'
	ans = 0
	for i in range(n):
		if l[i] == '1':
			ans += val[i]
	print(ans)


from bisect import bisect_left
from bisect import bisect_right
from getopt import getopt
import re
from tempfile import tempdir
from traceback import print_tb
from typing import DefaultDict
import math
from collections import Counter, defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import copy
import heapq
from collections import deque

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans

def ncr_modulo(n, r, p):
	num = 1
	den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return l

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def lcm(a, b):
	return a * b // math.gcd(a, b)

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def gcdList(l):
	a = l[0]
	for i in range(1, len(l)):
		a = math.gcd(a, l[i])
	return a

def check(a, size):
	max_so_far = -maxsize - 1
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	return [start, end]

def solve(t):
	s = input()
	n = len(s)
	l = []
	a = s[0]
	curr = n
	for i in range(1, n):
		if s[i] == a:
			curr += (i + 1) * (n - i)
		else:
			if a == '0':
				l.append(curr)
			else:
				l.append(-curr)
			a = s[i]
			curr = (i + 1) * (n - i)
	if a == '0':
		l.append(curr)
	else:
		l.append(-curr)
	[start, end] = check(l, len(l))
	if len(l) == 1:
		return abs(l[0])
	ans = 0
	for i in range(len(l)):
		if i >= start and i <= end:
			if l[i] > 0:
				ans += abs(l[i])
		elif l[i] < 0:
			ans += abs(l[i])
	return ans
for t in range(1, int(input()) + 1):
	print(solve(t))


for _ in range(int(input())):
	s = input()
	n = len(s)
	s = [el for el in s]
	diff = []
	for (i, el) in enumerate(s):
		if s[i] == '1':
			diff.append((i + 1) * (n - i))
			diff[-1] *= -1
		else:
			diff.append((i + 1) * (n - i))
	ans = abs(sum([el for el in diff if el <= 0]))
	l = 0
	temp = 0
	res = 0
	for r in range(n):
		temp += diff[r]
		while temp < 0:
			temp -= diff[l]
			l += 1
		res = max(res, temp)
	print(ans + res)