题目描述

在魔法学院的长桌上放着 $n$ 件魔法道具，依次排成一行。每一件道具都是“魔法面包”（用大写字母 M 表示）或者“神秘洋葱”（用大写字母 Y 表示）。已知至少有一件魔法面包和一件神秘洋葱。

你和朋友准备分这些道具：你取前$k$个道具，你朋友取剩下的道具。分配时必须满足以下三个规则：

1. 你和朋友都必须至少拿到一件道具；
2. 你获得的魔法面包数量与朋友获得的不同；
3. 你获得的神秘洋葱数量与朋友获得的不同。
4. 你获得的道具数量要不少于朋友的道具数量。

请你找出一个满足条件的分割点，输出你应该取多少个道具。如果存在多个答案，输出你拿的道具数量最少的一个。如果无法完成这样的分配，输出 $-1$。

输入格式

第一行一个整数 $n$——表示道具的总数。 第二行一个长度为 $n$ 的字符串，仅包含字符 'M' 和 'Y'，第 $i$ 个字符表示第 $i$ 件道具的类型。

保证至少有一个 'M' 和一个 'Y'。

输出格式

输出一个整数 $k$，表示你取前 $k$ 个道具可以满足条件。如果无解，输出 $-1$。

输入输出样例

3
MYM

-1

2
MY

1

10
MMYYYYMMMY

5

数据范围

对于前$30\%$的数据：$n \leq 200$， 对于前$60\%$的数据：$n \leq 2000$， 对于$100\%$的数据：$n \leq 10^{5}$，字符串只由M和Y组成。