Боб вже рік займається танцями, тому він має виступити на шоу талантів. Він вже написав номер, але несподівано помітив, що в його записах є помилки. Боб починає танцювати біля лівої стіни і робить послідовні кроки вліво і вправо в деякому порядку так, щоб закінчити танець в тому самому місці, в якому Боб почав, і так, щоб не врізатися в стіну(тобто, якщо він стоїть в початковому місці, то не може зробити крок вліво).
Записи Боба - це послідовність з символів ~L~ і ~R~, які позначають рухи вліво і вправо відповідно. Щоб виправити свої записи, він може зробити декілька операцій, кожна з яких буде наступного вигляду:

• вибрати підрядок і циклічно зсунути його вправо(наприклад, "LRL" -> "LLR"),

• або поставити символ "L" або "R" в будь якому місці послідовності.

Мінімальну кількість операцій для того, щоб виправити запис так, щоб по ньому можна було виступити, назвемо важкістю.
Боб ще не впевнений на рахунок свого танцю, тому він просить вас порахувати суму важкості всіх підрядків його запису.

Input

Перший рядок містить число ~n~ ~(1 \le n \le 2*10^5)~ - довжина запису Боба.

Наступний рядок містить послідовність з літер "L" і "R" - його запис.

Output

Виведіть одне ціле число - суму важкості всіх підрядків запису Боба.

Sample Input 1

6
RLRLRL

Sample Output 1

15

Примітка

У першому прикладі є наступні підрядки:

• {L} -> {RL} - одна операція, таких підрядків є 3
• {R} -> {RL} - одна операція, таких підрядків є 3
• {RL} -> {RL} - нуль операцій
• {LR} -> {RL} - одна операція, таких підрядків є 2
• {RLR} -> {RLRL} - одна операція, таких підрядків - 2
• {LRL} -> {RLRL} - одна операція, таких підрядків - 2
• {LRLR} -> {RLRL} - одна операція
• {RLRL} -> {RLRL}
• {RLRLR} -> {RLRLRL} - одна операція
• {LRLRL} -> {RLRLRL} - одна операція
• {RLRLRL} -> {RLRLRL}

Відповідь буде наступною: ~1 \times 3 + 1 \times 3 + 1 \times 2 + 1 \times 2 + 1 \times 2 + 1 + 1 + 1 = 15~