Задача C. Вася и конструктор чисел

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

У Васи есть любимый конструктор чисел. Он представляет из себя табличку длины N и неограниченный запас цифр от 0 до 9.

Для каждого числа Вася считает его крутость. Крутость  — это сумма произведений всех пар соседних цифр в числе, но при этом числа, в которых рядом стоят две одинаковые цифры, всегда имеют крутость 0. Вася очень любит играть с конструктором, поэтому он износился, и в некоторых позициях застряли цифры. Вася хочет узнать, насколько максимальная крутость числа в изношенном конструкторе меньше крутости самого крутого числа в новом конструкторе, в котором нет застрявших цифр.

Пояснение к примерам.

Рассмотрим тест №3: даны 99999 - это "заевшие" цифры в изношенном конструкторе, получается, что крутость изношенного конструктора Для этого примера = 0, т.к. все цифры одинаковые. Для нового конструктора "шаблон" числа будет выглядеть как *****, куда, следуя логики Поиска максимальной суммы произведения, мы ставим 98989, получая 9*8 + 8*9 + 9*8 + 8*9 = 288. Ответ: 288 - 0 = 288

Формат входного файла

В первой строке записано число 1 ≤ N ≤ 105. Во второй строке содержится S длины N, в которой на позиции i стоит * если позиция свободна, и на неё можно ставить любую цифру, в противном случае на i-й позиции записана цифра от 0 до 9.

Формат выходного файла

Выведите единственное целое число: разницу между крутостью самого крутого числа в новом конструкторе и конструкторе Васи.

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
***
0
2
5
1*1*1
252
3
5
99999
288

0.040s 0.009s 15