logo AlgoBeat OnlineJudge
登录 注册

#216139. [USTCPC 2026] Line of Pac-Man

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

“呜哇——!为什么吃豆人会从我的便当里钻出来啊!”

克露丝卡尔酱惊恐地看着手中的三明治,上面密密麻麻的芝麻粒突然变成无数微小的吃豆人,疯狂地左右移动!更诡异的是,空气中浮现出豆子形状的光点,被它们一个个吞噬。

“这难道是宇宙的真理?”克露丝卡尔酱颤抖着掏出笔记本,决定计算出最少会被吃掉多少豆子……


线段 的整点上分布了一些豆子和吃豆人。吃豆人有两种:一种以单位速度向左移动,一种以单位速度向右移动。当吃豆人经过豆子时,豆子会被吃掉。当两个吃豆人相遇时,你需要选择其中一个吃豆人,让它把另一个吃豆人吃掉,留下的那个吃豆人的移动方向不变。

请求出:最少一共会吃掉多少豆子?

注意:吃豆人的位置可以连续变化,而非离散的。

输入格式

本题有多组测试数据。

首先输入一行,包含一个整数 (),表示测试数据组数。

每组数据首先输入一行,包含一个整数,表示线段右端点 ()。

之后输入一行,包含一个长度为 的字符串,字符串仅包含 .o<> 四种字符,分别表示空格、豆子、向左移动的吃豆人、向右移动的吃豆人。

保证

输出格式

输出 行,每行一个整数,表示最少一共会吃掉多少豆子。

样例

样例输入 1

2
6
o>.<oo
2
<>

样例输出 1

1
0

数据范围与提示

在第一组样例中,当两个吃豆人相遇时选择保留向左移动的吃豆人,这样最终只有最左边的豆子被吃掉,因此答案为