Во новата зграда на Факултетот за информатички науки и компјутерско инженерство (ФИНКИ) просториите во кои се држат предавања се организирани на начин што, во секоја од нив, постои една голема кружна структура од единечни клупи на која што седат сите студенти ("тркалезна маса" со дупка во средината за професорот). Професорот кој држи предавање се наоѓа во средината на кружната структура помеѓу сите студенти..

Часовите на ФИНКИ се интерактивни, и често постои дискусија помеѓу учениците. Поради тоа, тие постојано се вртат налево или надесно за да го гледаат студентот кој зборува во тој момент и задолжително до почетокот на последниот час добиваат болки во вратот.

За несреќа, професорот Емир го држи последниот час. Тој мора да им дозволи на студентите наместо право кон него (кон центарот на кружната структура) да гледаат или налево или надесно, во зависност од која страна од вратот ги боли. При таквото позиционирање се добиваат парови студенти кои се еден кон друг свртени лице во лице. Бидејќи во таква позиција тие може да паднат во искушение да си дискутираат меѓусебно за најразлични работи, од АЈО до ШЈО, за ваквите парови ќе кажеме дека се "лоши".

Емир сака да ги размести учениците на клупите, така што бројот на лоши парови е најмал можен (барање 1). Со цел да не се прави голема гужва во просторијата, Емир ќе преместува студенти само на еден начин – преку замени на местата на студенти кои се наоѓаат еден до друг на кружната структура. Напишете програма која покрај пресметката на барањето 1 (најмалиот можен број на лоши парови), ќе го одреди и најмалиот број на замени на местата кои треба да се направат за доаѓање до таа ситуација (на најмал број лоши парови).

Влез

Во првата линија е запишан еден цел број N (1 <= N <= 100 000), кој го означува бројот на студенти.

Во втората линија се запишани N знаци (L или D), кои означуваат како е свртен секој од студентите– налево (L) или надесно (D). Студентите се дадени во редослед според нивната поставеност на кружната структура. Нормално, покрај тоа што првиот студент се наоѓа до вториот, вториот до третиот, третиот до четвртиот итн, на кружната структура се соседни и последниот со првиот студент.

Како што наведовме, лоши парови се оние каде имаме студент кој гледа надесно, а веднаш десно од него имаме студент кој гледа налево, со што тие се свртени лице во лице ("DL" пар).

Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 10.

Излез

Отпечатете ги двата барани податока, одделени со празно место.

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

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

Примери

влез
5
LLLLL

излез
0 0

влез
4
DLLD

излез
1 0

влез
7
DLDDLDD

излез
1 2

Објаснување за првиот пример: Сите студенти се свртени налево, па нема ниту еден лош пар.

Објаснување за вториот пример: Иницијално, на кружната структура има еден лош пар. Што и да направиме, не можеме да ги организираме студентите така што ќе нема лош пар.

Објаснување за третиот пример: Дозволено е само да се заменуваат местата на соседни парови. Доколку прво го преместиме вториот студент (гледано од лево надесно во листата) со третиот студент, ќе дојдеме до следната ситуација: DDLDLDD. Сега, истиот студент се наоѓа на третата позиција, па можеме да му го замениме местото со студентот на четвртата позиција, по што имаме: DDDLLDD. На вака поставен кружна структура постои само еден (1) лош пар, а до овој распоред дојдовме со две (2) замени.