Problem F
Speedrunning
Mario has recently discovered that the physics engine has gotten an update: he can now run faster when he’s in Small Mario form. This has caused quite the headache for speedrunners.
For simplicity, we consider the level to be a $1\times N$ grid of tiles. Mario starts at the first tile, and completes the level when he reaches the $N$-th tile.
On each tile, there can be either a question block (denoted ‘?’), a saw (denoted ‘S’), or neither (denoted by ‘.’). It is guaranteed that the first tile and $N$-th tile are empty.
Mario can take one of three forms: Small Mario, Super Mario, or Fire Mario. To move one tile forward, the movement takes Small Mario $1$ game tick, but it takes Super Mario and Fire Mario $2$ game ticks. Mario is not considered to have reached a tile until the end of his movement and Mario is unable to move backwards (it wouldn’t be a speedrun if he was moving backwards).
When Mario reaches a tile with a saw on it, he activates the saw and takes damage (the saws are unavoidable). This causes the following behavior:
-
If Mario is in Small Mario form, he dies.
-
If Mario is in Super Mario form, he becomes Small Mario.
-
If Mario is in Fire Mario form, he becomes Super Mario.
When Mario reaches a question block, he can choose to activate it, causing the following behavior if he activates it:
-
If Mario is in Small Mario form, he becomes Super Mario.
-
If Mario is in Super Mario form, he becomes Fire Mario.
-
If Mario is in Fire Mario form, nothing happens.
Interactions with saws and question blocks both take $0$ game ticks. That is, when Mario reaches and activates them, Mario will instantly change his form and update his speed. It is impossible for Mario to activate the same saw twice, or the same question block twice.
Speedrunners now face the difficult choice of min-maxing whether or not they should activate each question block. To make matters even more complicated, players are allowed to start in any of the $3$ Mario forms. Being in Small Mario form allows them to run faster, but running faster won’t matter if they die before reaching the end.
Given optimal play, is it possible to complete the level, and if so, what is the minimum amount of game ticks required to successfully complete the level?
Input
The first line of input is an integer $2 \leq N \leq 200\, 000$.
The second line of input is a string of length $N$, consisting of only the characters ‘.’, ‘?’, and ‘S’. The first and last characters are guaranteed to be ‘.’.
Output
Output a single integer denoting the minimum amount of game ticks required to successfully complete the level, or $-1$ if it is impossible to complete the level.
Explanation for Sample Input 1: Mario should start the level on the 1st tile as Super Mario. In this form, it takes 2 ticks for a movement. Thus, Mario reaches the 2nd tile after 2 ticks. The saw instantly activates, and Mario becomes Small Mario. It now takes him only 1 tick to complete a movement. He reaches the 3rd tile in one additional tick, and reaches the 4th and final tile in one more tick. Thus, it takes him a total of 2+1+1 = 4 ticks.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 .S.. |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 .?.?S. |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 .SS?SS. |
-1 |
