背景

    有两种液体A和B,等量混合时完全反应生成气体挥发不留渣;不等量混合时等量部分发生上述反应,多出部分留下。

描述

    现有n个杯子排成一排,每个杯子里装有一种液体。我们可以进行若干次如下操作:选择两个相邻的杯子,这两个杯子中的液体种类必须是不同的,将其中一个杯子里的液体全部倒入另一个杯子中(杯子容积很大,不考虑溢出),反应充分之后拿走所有空杯子(拿走空杯子可以使原本不相邻的杯子变得相邻)。给出一个初始状态,求最少剩下多少个杯子。

输入格式

    输入有n+1行,第一行有一个正整数n,接下来的n行,每行格式为“Vi Ki”,Vi为一正整数,表示这排杯子从左数第i个杯子的液体量,Ki为一个字符A或B,表示这排杯子从左数第i个杯子里液体的种类。

输出格式

    输出有一个整数,表示最少剩下的杯子数。

样例输入

4
4 B
2 A
1 A
3 B

样例输出

1

数据范围与约定

  • 20%的数据,0<n≤5。
  • 40%的数据,0<n≤100。
  • 60%的数据,0<n≤1000。
  • 100%的数据,0<n≤100000,0<Vi≤10000。

样例解释

    将第三个杯子中的液体倒入第四个杯子,拿走第三个杯子,再将第二个杯子中的液体倒入第四个杯子,拿走第二个和第四个杯子,剩余第一个杯子。

来源

原创