P16236 [Lanqiao Cup 2026 NOI Qualifier B] LQ Aggregation

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.

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 one integer, representing the maximum number of “$LQ$ aggregations” that can be obtained after replacing all `?` with `L` or `Q`.

### 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