310951: CF1912L. LOL Lovers

L. LOL Loverstime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

There are $n$ food items lying in a row on a long table. Each of these items is either a loaf of bread (denoted as a capital Latin letter 'L' with ASCII code 76) or an onion (denoted as a capital Latin letter 'O' with ASCII code 79). There is at least one loaf of bread and at least one onion on the table.

You and your friend want to divide the food on the table: you will take a prefix of this row (several leftmost items), and the friend will take the rest. However, there are several restrictions:

1. Each person should have at least one item.
2. The number of your loaves should differ from the number of your friend's loaves.
3. The number of your onions should differ from the number of your friend's onions.

Find any correct division and print the number of items you take or report that there is no answer.Input

The first line contains one integer $n$ ($2 \le n \le 200$) — the number of food items on the table. The second line contains a string of length $n$ consisting of letters 'L' and 'O'. $i$-th symbol represents the type of the $i$-th food item on the table: 'L' stands for a loaf of bread, and 'O' stands for an onion. It is guaranteed that this string contains at least one letter 'L' and at least one letter 'O'.

Output

Print one integer — a number $k$ such that, if you take $k$ leftmost items and your friend takes the remaining $n - k$ items, each of you and your friend get at least one item, your number of loaves is different from your friend's, and your number of onions is different from your friend's. If there are several possible answers, print any of them. If there are no possible answers, print the number $-1$.

ExamplesInput

3
LOL

Output

-1

Input

2
LO

Output

1

Input

4
LLLO

Output

1

Input

4
OLOL

Output

-1

Input

10
LLOOOOLLLO

Output

5

Note

In the first example, in any division the left and the right part contain one loaf of bread.

In the second example, the division is 'L' and 'O', and in these two strings the number of loaves is different (1 and 0) and the number of onions is different (0 and 1).

In the third example, any number 1, 2 or 3 is a correct answer.

题目大意：
在一张长桌子上有一行排列着n份食物，每份食物要么是一块面包（用大写拉丁字母'L'表示，ASCII码为76），要么是一个洋葱（用大写拉丁字母'O'表示，ASCII码为79）。桌子上至少有一块面包和一个洋葱。你和一个朋友想要平分桌子上的食物：你将拿走这一行的前缀部分（最左边的几份），你的朋友将拿走剩下的部分。但是有一些限制：
1. 每个人至少应该有一份食物。
2. 你拥有的面包数量应该与你的朋友不同。
3. 你拥有的洋葱数量应该与你的朋友不同。

找出任何正确的分配方案，并打印出你拿走的食物数量，或者报告没有答案。

输入数据格式：
第一行包含一个整数n（2≤n≤200）——桌子上的食物数量。第二行包含一个长度为n的字符串，由字母'L'和'O'组成。第i个符号代表桌子上第i个食物的类型：'L'代表一块面包，'O'代表一个洋葱。保证这个字符串至少包含一个字母'L'和一个字母'O'。

输出数据格式：
打印一个整数k，使得如果你拿走最左边的k份食物，你的朋友拿走剩下的n-k份食物，你和你的朋友都至少得到一份食物，你拥有的面包数量与你的朋友不同，你拥有的洋葱数量也与你的朋友不同。如果有多个可能的答案，打印其中任何一个。如果没有可能的答案，打印数字-1。

例：
输入：
3
LOL
输出：
-1

输入：
2
LO
输出：
1

输入：
4
LLLO
输出：
1

输入：
4
OLOL
输出：
-1

输入：
10
LLOOOOLLLO
输出：
5

注意：
在第一个例子中，任何分配方案中左部和右部都包含一块面包。
在第二个例子中，分配方案是'L'和'O'，在这两个字符串中面包的数量不同（1和0）和洋葱的数量不同（0和1）。
在第三个例子中，任何数字1、2或3都是正确答案。题目大意： 在一张长桌子上有一行排列着n份食物，每份食物要么是一块面包（用大写拉丁字母'L'表示，ASCII码为76），要么是一个洋葱（用大写拉丁字母'O'表示，ASCII码为79）。桌子上至少有一块面包和一个洋葱。你和一个朋友想要平分桌子上的食物：你将拿走这一行的前缀部分（最左边的几份），你的朋友将拿走剩下的部分。但是有一些限制： 1. 每个人至少应该有一份食物。 2. 你拥有的面包数量应该与你的朋友不同。 3. 你拥有的洋葱数量应该与你的朋友不同。 找出任何正确的分配方案，并打印出你拿走的食物数量，或者报告没有答案。 输入数据格式： 第一行包含一个整数n（2≤n≤200）——桌子上的食物数量。第二行包含一个长度为n的字符串，由字母'L'和'O'组成。第i个符号代表桌子上第i个食物的类型：'L'代表一块面包，'O'代表一个洋葱。保证这个字符串至少包含一个字母'L'和一个字母'O'。 输出数据格式： 打印一个整数k，使得如果你拿走最左边的k份食物，你的朋友拿走剩下的n-k份食物，你和你的朋友都至少得到一份食物，你拥有的面包数量与你的朋友不同，你拥有的洋葱数量也与你的朋友不同。如果有多个可能的答案，打印其中任何一个。如果没有可能的答案，打印数字-1。 例： 输入： 3 LOL 输出： -1 输入： 2 LO 输出： 1 输入： 4 LLLO 输出： 1 输入： 4 OLOL 输出： -1 输入： 10 LLOOOOLLLO 输出： 5 注意： 在第一个例子中，任何分配方案中左部和右部都包含一块面包。 在第二个例子中，分配方案是'L'和'O'，在这两个字符串中面包的数量不同（1和0）和洋葱的数量不同（0和1）。 在第三个例子中，任何数字1、2或3都是正确答案。