Taco: Minimum Moves on a Block Path

You are given a path consisting of N blocks arranged in a row. Each block is represented by a character in a string S of length N. A block may be:

• . indicating a safe block,
• B representing a bomb, or
• O denoting an obstacle.

You start at block index 0 and want to reach block index N-1. However, if the first or last block is not safe (i.e. if it is either B or O), the journey is impossible. At each move, you try to step from your current position i to i+1:

• If the next block is safe (.), you move forward.
• If the next block contains a bomb (B), you must backtrack to the nearest safe block before it. Formally, you set a pointer j starting from i and decrement it until you find a block that is not safe to backtrack from. If no such safe block exists (i.e. j becomes 0), then the path is impassable.
• If the next block has an obstacle (O), you cannot proceed, and the answer is -1.

Your task is to compute the minimum number of moves required to traverse from the start to the end of the blocks if possible. Otherwise, output -1.

In mathematical terms, if we denote the number of moves by M, then the answer is given by:

[ M = \begin{cases} \text{the minimum number of moves required to reach index } N-1, & \text{if a valid path exists};\ -1, & \text{if no valid path exists.} \end{cases} ]

inputFormat

The input is given via standard input. The first line contains an integer N (\(1 \le N \le 10^3\)), the number of blocks. The second line contains a string S of length N representing the blocks. The characters in S are among ., B, and O.

outputFormat

Print a single integer to standard output representing the minimum number of moves required to traverse from block index 0 to block index N-1. If it is impossible to complete the journey, print -1.

## sample

8
........

7