经过辛苦的一天后,维塔利非常饿,他想吃他最喜欢的土豆派。但事情没那么简单。维塔利在房子的第一个房间里,有n个房间排成一排,从左到右从一个开始编号。你可以从第一个房间到第二个房间,从第二个房间到第三个房间,依此类推——你可以从第 (n - 1) 个房间到第 n 个房间。因此,您只能从房间 x - 1 前往房间 x。
土豆派位于第n个房间,维塔利需要去那里。
每对连续的房间之间都有一扇门。为了从房间x - 1去房间x,你需要用相应的钥匙打开房间之间的门。
房子总共有几种类型的门(用大写拉丁字母表示)和几种类型的钥匙(用小写拉丁字母表示)。当且仅当 t 和 T 是同一个字母,但写法不同时,t 类型的钥匙才能打开 T 类型的门。例如,钥匙f可以打开门F。
前 n - 1 个房间中的每一个都恰好包含一把某种类型的钥匙,Vitaly 可以使用它进入下一个房间。一旦用钥匙打开门,维塔利不会从钥匙孔中拿到钥匙,但他会立即跑进隔壁房间。换句话说,每把钥匙只能打开一扇门。
维塔利意识到他最终可能会进入某个房间,却没有打开下一个房间门的钥匙。在开始争夺土豆派之前,维塔利可以购买任意数量、任意类型的钥匙,以保证到达 n 号房间。
考虑到房子的平面图,Vitaly 想知道他至少需要购买多少把钥匙才能确保到达 n 号房间,那里有美味的土豆饼。编写一个程序来帮助维塔利找出这个数字。
输入
输入的第一行包含一个正整数 n (2 ≤ n ≤ 105) — 房子的房间数。
输入的第二行包含长度为 2·n - 2 的字符串 s。让我们从左到右对字符串的元素进行编号,从 1 开始。
给定字符串 s 中的奇数位置包含小写拉丁字母——相应房间中钥匙的类型。因此,给定字符串 s 的每个奇数位置 i 都包含一个小写拉丁字母——房间号 (i + 1) / 2 中钥匙的类型。
给定字符串中的偶数位置包含大写拉丁字母 - 房间之间的门的类型。因此,给定字符串 s 的每个偶数位置 i 都包含一个大写字母——从房间 i / 2 通向房间 i / 2 + 1 的门的类型。
输出
打印唯一的整数——Vitaly 需要购买的钥匙的最小数量才能确保从 1 号房间到达 n 号房间。
示例
输入 #1
3 aAbB
输出 #1
0
输入 #2
4 aBaCaB
输出 #2
3
输入 #3
5 xYyXzZaZ
输出 #3
2