CF1936B.Pinball

There is a one-dimensional grid of length $n$. The $i$-th cell of the grid contains a character $s_i$, which is either '<' or '>'.

When a pinball is placed on one of the cells, it moves according to the following rules:

• If the pinball is on the $i$-th cell and $s_i$ is '<', the pinball moves one cell to the left in the next second. If $s_i$ is '>', it moves one cell to the right.
• After the pinball has moved, the character $s_i$ is inverted (i. e. if $s_i$ used to be '<', it becomes '>', and vice versa).
• The pinball stops moving when it leaves the grid: either from the left border or from the right one.

You need to answer $n$ independent queries. In the $i$-th query, a pinball will be placed on the $i$-th cell. Note that we always place a pinball on the initial grid.

For each query, calculate how many seconds it takes the pinball to leave the grid. It can be shown that the pinball will always leave the grid within a finite number of steps.

有一个长度为 $n$ 的一维网格。网格的第 $i$ 个单元格中包含一个字符 $s_i$，该字符为 '<' 或 '>'。

当弹珠被放置在某个单元格上时，它将按照以下规则移动：

• 若弹珠位于第 $i$ 个单元格且 $s_i$ 为 '<'，则弹珠在下一秒向左移动一个单元格；若 $s_i$ 为 '>'，则向右移动一个单元格。
• 弹珠移动后，字符 $s_i$ 将被翻转（即若 $s_i$ 原为 '<'，则变为 '>'；反之亦然）。
• 当弹珠离开网格（即从左边界或右边界移出）时，其运动停止。

你需要回答 $n$ 个相互独立的查询。在第 $i$ 个查询中，弹珠将被放置在第 $i$ 个单元格上。注意：我们始终将弹珠放置在初始网格上。

对每个查询，请计算弹珠离开网格所需的时间（以秒为单位）。可以证明，弹珠总会在有限步内离开网格。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line of each test case contains a string $s_1s_2 \ldots s_{n}$ of length $n$ consisting of characters '<' and '>'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s_1s_2 \ldots s_{n}$，该字符串仅由字符 '<' 和 '>' 组成。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

For each test case, for each $i$ ($1 \le i \le n$) output the answer if a pinball is initially placed on the $i$-th cell.

对于每个测试用例，对每个 $i$（$1 \le i \le n$），输出当弹珠初始放置在第 $i$ 个格子时的答案。

In the first test case, the movement of the pinball for $i=1$ is shown in the following pictures. It takes the pinball $3$ seconds to leave the grid.

The movement of the pinball for $i=2$ is shown in the following pictures. It takes the pinball $6$ seconds to leave the grid.

在第一个测试用例中，小球在 $i=1$ 时的运动过程如下图所示。小球离开网格共耗时 $3$ 秒。

小球在 $i=2$ 时的运动过程如下图所示。小球离开网格共耗时 $6$ 秒。