Monotonicity 2

For an integer sequence $a_1, a_2, \ldots, a_n$, its monotonicity scheme is the sequence $s_1, s_2, \ldots, s_{n-1}$ where each $s_i$ describes how $a_i$ compares with $a_{i+1}$: it is $<$ when $a_i < a_{i+1}$, $>$ when $a_i > a_{i+1}$, and $=$ when $a_i = a_{i+1}$. For example, the monotonicity scheme of $2, 4, 3, 3, 5, 3$ is $<, >, =, <, >$.

A sequence with monotonicity scheme $s_1, s_2, \ldots, s_n$ realizes a scheme $s'_1, s'_2, \ldots, s'_k$ when $s_i = s'_{((i-1) \bmod k) + 1}$ for every $i = 1, 2, \ldots, n$. Equivalently, $s_1, s_2, \ldots, s_n$ is what you get by writing out $s'_1, s'_2, \ldots, s'_k$ over and over and then cutting off a suffix. For instance, $2, 4, 3, 3, 5, 3$ realizes all of $<, >, =$ and $<, >, =, <, >$ and $<, >, =, <, >, <, <, =$, among many others.

You are given an integer sequence $a_1, a_2, \ldots, a_n$ and a monotonicity scheme $s_1, s_2, \ldots, s_k$. Among all subsequences $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ with $1 \le i_1 < i_2 < \cdots < i_m \le n$ whose own monotonicity scheme realizes $s_1, s_2, \ldots, s_k$, find the largest possible length $m$. A subsequence of a single element (with an empty monotonicity scheme) always realizes the scheme, so the answer is at least $1$.

The first line contains two integers $n$ and $k$ ($1 \le n \le 500{,}000$, $1 \le k \le 500{,}000$): the length of the sequence and the length of the monotonicity scheme.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1{,}000{,}000$), separated by single spaces.

The third line contains $k$ symbols $s_1, s_2, \ldots, s_k$, each one of $<$, $>$, or $=$, separated by single spaces.

Print one integer: the maximum length $m$ of a subsequence of $a_1, a_2, \ldots, a_n$ whose monotonicity scheme realizes $s_1, s_2, \ldots, s_k$.