Under construction

Still being built. Things may change

Bonus Score

Interview

Time limit1sMemory limit512 MB

Summary
Given a string of O and X for N problems, compute the total score where problem i gives i points plus a running bonus that grows on each O and resets on each X.
Level

Easy2 of 10

Topics
Implementation, Simulation, String
Solved
No attempts yet

Problem

The Sookgoahan Algorithm Camp quiz time has begun! This mini contest covers a huge range of topics: PS basics, dynamic programming, parametric search, Wookje's birthday, search, greedy algorithms, shortest path algorithms, Gudeogi Cup, disjoint set, minimum spanning tree, lowest common ancestor, segment tree, how to generate high-quality random numbers in C++ on Codeforces, maximum flow, convex hull, and more. It shines today as ever with the challenges of countless participants, and the number of submitted OX sheets is beyond counting.

The organizers have to grade these OX sheets, compute the scores, and then hold the awards ceremony to wrap up the event in a warm atmosphere. In the Sookgoahan Algorithm Camp quiz time, the score of an OX sheet is computed as follows.

  • When an OX sheet has N problems, they are graded in the order problem 1, problem 2, ..., problem N.

  • Since problems get harder toward the end, the base score of problem i is i points.

    • If you solve the problem, you gain its base score (that is, i points for problem i); if you get it wrong, you gain nothing.

  • Apart from the base score, there is a value called the 'bonus score'. It starts at 0 points.

    • If you solve a problem, you gain the current 'bonus score', and the value of the 'bonus score' increases by 1 point.
    • If you get a problem wrong, you gain no 'bonus score', and the value of the 'bonus score' resets to 0 points.

Minsung happened to take on the job of grading the OX sheets of the Sookgoahan Algorithm Camp quiz time. Dreading the thought of looking at countless OX sheets, Minsung decides to write a program to automate this. Let's help Minsung, who has only 4 hours left until the awards ceremony, compute the scores.

Input

The first line gives a natural number N, the length of the OX sheet. (1 ≤ N ≤ 10,000)

The second line gives a string S representing the OX sheet. S consists only of O (uppercase letter O, ASCII code 79) and X (uppercase letter X, ASCII code 88), and its length is N.

If the i-th character of string S is O, it means the participant solved the i-th problem; if it is X, it means they got it wrong.

Output

On the first line, print the score of the OX sheet given as input.

Examples1

  1. Example 1

    Input
    8
XOOOXOOX
    Expected output
    26