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

Условие

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

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

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

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

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

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

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

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

Ограничения

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

3
***

0

5
1*1*1

252

5
99999

288