codeforces#P1776N. Count Permutations

Count Permutations

Description

You are given a string $s$ with length $n-1$ whose characters are either $\texttt{<}$ or $\texttt{>}$.

Count the permutations $p_1, \, p_2, \, \dots, \, p_n$ of $1, \, 2, \, \dots, \, n$ such that, for all $i = 1, \, 2, \, \dots, \, n - 1$, if $s_i$ is $\texttt{<}$ then $p_i < p_{i+1}$ and if $s_i$ is $\texttt{>}$ then $p_i > p_{i+1}$.

Since this number can be very large, compute its logarithm in base $2$.

The first line contains a single integer $n$ ($2 \le n \le 100\,000$).

The second line contains a string $s$ of length $n-1$; each character of $s$ is either $\texttt{<}$ or $\texttt{>}$.

Print the logarithm in base $2$ of the number of permutations satisfying the constraints described in the statement.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally, let your answer be $x$ and let the correct answer be $y$. Your answer is accepted if and only if $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$.

Input

The first line contains a single integer $n$ ($2 \le n \le 100\,000$).

The second line contains a string $s$ of length $n-1$; each character of $s$ is either $\texttt{<}$ or $\texttt{>}$.

Output

Print the logarithm in base $2$ of the number of permutations satisfying the constraints described in the statement.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally, let your answer be $x$ and let the correct answer be $y$. Your answer is accepted if and only if $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$.

2
&lt;
3
&lt;&gt;
5
&gt;&lt;&lt;&lt;
10
&lt;&gt;&lt;&lt;&lt;&lt;&lt;&gt;&gt;
0.0000000000
1.0000000000
2.0000000000
9.8281364842

Note

In the first sample, there is only one valid permutation, that is $[2, 1]$. Since $\log_2(1)=0$, the correct output is $0$.

In the second sample, there are $2$ valid permutations, that are $[3, 1, 2]$ and $[2, 1, 3]$. Since $\log_2(2)=1$, the correct output is $1$.

In the third sample, there are $4$ valid permutations, that are $[1, 5, 4, 3, 2]$, $[2, 5, 4, 3, 1]$, $[3, 5, 4, 2, 1]$, $[4, 5, 3, 2, 1]$. Since $\log_2(4)=2$, the correct output is $2$.

In the fourth sample, there are $909$ valid permutations. Notice that $\log_2(909)=9.828136484194\ldots$