Problem D
Purple Rain
On close observation however, Prof. Nelson Rogers finds that actually it is a mix of Red and Blue drops.
In his zeal, he records the location and color of the raindrops in different locations along the peninsula. Looking at the data, Professor Rogers wants to know which part of Linearland had the “least” purple rain.
After some thought, he decides to model this problem as follows. Divide the peninsula into $n$ sections and number them West to East from $1$ to $n$. Then, describe the raindrops as a sequence of R and B, depending on whether the rainfall in each section is primarily red or blue. Finally, find a subsequence of where the difference between the number of R and the number of B is maximized.
Input
The input consists of a single line containing a string of $n$ characters ($1 \le n \le 10^5$), describing the color of the raindrops in sections $1$ to $n$.
It is guaranteed that the string consists of uppercase ASCII letters ‘R’ and ‘B’ only.
Output
Print, on a single line, two space-separated integers that describe the starting and ending positions of the part of Linearland that had the least purple rain.
If there are multiple possible answers, print the one that has the Westernmost (smallest-numbered) starting section. If there are multiple answers with the same Westernmost starting section, print the one with the Westernmost ending section.
| Sample Input 1 | Sample Output 1 |
|---|---|
BBRRBRRBRB |
3 7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
BBRBBRRB |
1 5 |
