Бинарной строкой называется строка, состоящая только из символов 0 и 1. Вам дана бинарная строка \(s\).
Для некоторой непустой подстроки\(^\dagger\) \(t\) строки \(s\), состоящей из \(x\) символов 0 и \(y\) символов 1, определим её стоимость как:
- \(x \cdot y\), если \(x > 0\) и \(y > 0\);
- \(x^2\), если \(x > 0\) и \(y = 0\);
- \(y^2\), если \(x = 0\) и \(y > 0\).
Вам дана бинарная строка \(s\) длины \(n\), найдите максимальную стоимость среди всех её непустых подстрок.
\(^\dagger\) Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальную стоимость среди всех подстрок.
Примечание
В первом наборе входных данных мы можем взять подстроку \(111\). Она содержит \(3\) символа 1 и \(0\) символов 0. Таким образом, \(a = 3\), \(b = 0\), и её стоимость равна \(3^2 = 9\).
Во втором наборе входных данных мы можем взять всё строку. Она содержит \(4\) символа 1 и \(3\) символа 0. Таким образом, \(a = 4\), \(b = 3\), и её стоимость равна \(4 \cdot 3 = 12\).
В третьем наборе входных данных мы можем взять подстроку \(1111\), и её стоимость равна \(4^2 = 16\).
В четвёртом наборе входных данных мы можем взять всю строку. Её стоимость равна \(4 \cdot 3 = 12\).
В пятом наборе входных данных мы можем взять подстроку \(000\). Её стоимость равна \(3 \cdot 3 = 9\).
В шестом наборе входных данных мы можем взять только подстроку \(0\). Её стоимость равна \(1 \cdot 1 = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
|
9
12
16
12
9
1
|