РНК (рибонуклеинска киселина) е многу важна молекуларна структура која учествува во виталните процеси на клетките, особено при удвојувањето на DNA во рамки на клетката. Таа на некој начин го "организира" целиот процес на репликација на ДНК (деоксирибонуклеинска киселина) во рамки на клетката.

РНК претставува полинуклеотид составена од следниве нуклеотиди: A (Аденин), G (Гванин), U (Урацил) и C (Цитозин). Исто така се знае дека А и U, C и G, и G и U формираат дополнителни хемиски врски. Тоа значи дека се возможни врските A – U, U - A, C – G, G – C, G – U и U – G.

За да се одреди дводимензионална структура на ваквата сложена молекула потребно е да се одредат дополнителните врски меѓу нуклеотидите. Едно од најпростите предвидувања на овие врски е да се максимизира бројот на ваквите врски, при што важи правилото дека соседни нуклеотиди не смеат да создадат врска.

Молекулата на РНК се претставува како низа од горенаведните нуклеотиди. Ваша задача е за дадена низа од нуклеотиди да го максимизирате бројот на вакви дополнителни врски.

На пример, нека стрингот кој ја означува РНК секвенцата биде
AUGAAAGUCUAAGUACUUUAGCGGGACCGGGCCUAA

Тогаш максималниот број на дополнителни врски што можат да се направат се 14. Превиткувањето изгледа вака:

Влез

Во првата линија се наоѓа бројот N (5 <= N <= 200), којшто го означува број на нуклетиди во РНК стрингот. Во наредната линија е запишан РНК стрингот.

Излез

Излезот се состои од еден ред во кој треба да го отпечатите максималниот број на дополнителни врски што можат да се креираат.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
36
AUGAAAGUCUAAGUACUUUAGCGGGACCGGGCCUAA

излез
14