Поликарп любит строчные буквы и недолюбливает прописные. Однажды он получил строку s, состоящую только из строчных и прописных букв английского алфавита.
Пусть A — множество индексов строки. Назовем его симпатичным, если:
- в индексах из A стоят различные строчные буквы;
- в строке нет таких прописных (заглавных) букв, которые расположены между элементами из A (иными словами, не существует такого j, что s[j] — прописная буква и a1 < j < a2 для некоторых a1 и a2 из A).
Напишите программу, которая найдет наибольшее количество элементов симпатичного множества индексов.
Выходные данные
Выведите наибольшее количество элементов симпатичного множества индексов для строки s.
Примечание
В первом примере искомыми позициями могут являться позиции 6 и 8 или позиции 7 и 8. В позициях 6 и 7 стоит буква 'a', в позиции 8 стоит буква 'b'. Пара позиций 1 и 8 не подходит, так как между ними стоит прописная буква 'B'.
Во втором примере искомыми позициями, например, являются позиции 7, 8 и 11. Существуют и другие способы выбрать симпатичное множество, состоящее из трёх элементов.
В третьем примере строка s не содержит строчных букв, следовательно, ответ равен 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
aaaaBaabAbA
|
2
|
|
2
|
12
zACaAbbaazzC
|
3
|
|
3
|
3
ABC
|
0
|