Problema B - Eventos em cadeia

A Joana trabalha num laboratório de genética, e é uma das melhores investigadoras na sua área. Neste momento está a trabalhar com umas cadeias de DNA muito especiais que apenas contêm 2 tipos de nucleótidos! Uma cadeia de DNA é simplesmente uma sequência de carateres. Para simplificar, denominámos as bases de 'A' e 'T'.

Mais especificamente, a Joana está a estudar a maneira como estas bases se ligam. Para isso, precisa de contar o número de ligações nucleares 'AT' que aparecem na cadeia, isto é, o número de vezes que um caráter 'A' aparece antes de um 'T' em qualquer posição não necessariamente adjacente. Por exemplo, para AATAT esse número seria 5, pois os 2 primeiros A's tem 2 T's à frente e último apenas 1, sendo a resposta 2+2+1=5. A imagem seguinte mostra as ligações:

Infelizmente, a Joana também comete erros, e no processo de análise do DNA deixou cair a única amostra que tinha, perdendo parte desta. Desta forma, não tem a informação toda que necessita para terminar o seu estudo. Mas eis que aparece a sua salvação, tu e as tuas habilidades de programador podem ajudá-la!

A Joana precisa de informação sobre a cadeia original, e a única coisa que sabe, após olhar para o que resta, é que esta era a que maximizava o número de ligações nucleares 'AT'. Por exemplo, se a cadeia fosse T?A?TA?A o valor pretendido seria 7, obtido a partir da cadeia TAATTATA.

Dada a cadeia incompleta da Joana, consegues ajudá-la a obter informação sobre a sua cadeia original, ou seja, o número de ligações 'At' da cadeia que as maximiza?

O Problema

Dado uma cadeia de DNA com N carateres 'A', 'T' ou '?' calcular o número máximo de ligações nucleares quando substituimos os '?' por 'A' ou 'T'.

Input

O input consiste apenas em duas linhas. Na primeira linha o tamanho N da cadeia. Na segunda uma linha com N carateres.

Output

Uma linha com o valor pedido.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

A resposta pode ir até 2^62.

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Input do Exemplo 1

8
T?A?TA?A

Output do Exemplo 1

7

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

5
AATAT

Output do Exemplo 2

5

Input do Exemplo 3

5
?????

Output do Exemplo 3

6