No.2894 Monotonic Intervals
loop0919
hiro1729Problem Statement
You are given a string $S$ of length $N$ consisting of < , > . Here, $S_i$ denotes the $i$-th character of $S$.
Consider a real function $f(x)$ satisfying the following condition for all $i = 1, 2, \cdots, N$.
- For any real numbers $a, b$ satisfying $i - 1 \le a < b \le i$,
- if $S_i$ is
<, then $f(a) < f(b)$ holds. - if $S_i$ is
>, then $f(a) > f(b)$ holds.
Among real numbers $x$ satisfying $0 \le x \le N$, find the maximum possible number of $x$ such that $f(x) = 0$.
It can be proved that the answer is finite.
Input
$N$ $S$
The input satisfies all of the following constraints.
- $1 \le N \le 5 \times 10^5$
- $N$ is an integer.
- $S$ is a string of length $N$ consisting of
<,>.
Output
Print the answer.
Sample
Sample 1
Input
3 ><<
Output
2
For example, $f(x) = |x - 1| - 1$ is a function satisfying the condition. For this $f(x)$, we have $f(x) = 0$ at $x = 0, 2$.
It is impossible to have $3$ or more values of $x$ satisfying $f(x) = 0$, so print $2$, the maximum number of $x$ satisfying $f(x) = 0$.
Sample 2
Input
7 <<<<<<<
Output
1
Sample 3
Input
17 <<<<><>>><><<><<<
Output
9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。