Problem Description

In the year 2056, an expedition team discovered a signal transmission tower deep inside a crater on the far side of the Moon. Its core console is continuously flashing a particle sequence of length $N$.

Each position in the sequence is strictly defined as an $L$-type particle, a $Q$-type particle, or an unknown state $?$, blurred by the erosion of time. These particles will be injected into the reaction field one by one, and the stability of the field depends on the number of “$LQ$ aggregations” in the sequence. This number is defined as the count of all pairs $(i, j)$ satisfying $1 \le i < j \le N$, where the $i$-th position is $L$ and the $j$-th position is $Q$.

To restart this dormant giant tower, the expedition team needs to repair all $?$ in the sequence into definite $L$ or $Q$.

Now, please compute the maximum possible number of “$LQ$ aggregations” among all possible repair plans.

Input Format

The first line contains an integer $N$, representing the length of the particle sequence.

The second line contains a string of length $N$, consisting only of characters L, Q, and ?, representing the currently detected state of the particle sequence.

Output Format

Output one integer, representing the maximum number of “$LQ$ aggregations” that can be obtained after replacing all ? with L or Q.

5
??L??

6

Hint

Sample Explanation

One optimal strategy is to repair the sequence into LLLQQ. Then, the first $3$ L and the last $2$ Q can produce $3 \times 2 = 6$ aggregations in total.

Test Case Scale and Assumptions

For $30\%$ of the test cases, the number of ? in the string does not exceed $10$.

For all test cases, $2 \le N \le 10^5$.

Translated by ChatGPT 5