단조성 2

정수 수열 $a_1, a_2, \ldots, a_n$에 대해, 이 수열의 단조성 표현을 기호 $s_1, s_2, \ldots, s_{n-1}$의 수열로 정의한다. 각 기호 $s_i$는 $a_i$와 $a_{i+1}$의 대소 관계를 나타내며, $a_i < a_{i+1}$이면 $<$, $a_i > a_{i+1}$이면 $>$, $a_i = a_{i+1}$이면 $=$이다. 예를 들어 수열 $2, 4, 3, 3, 5, 3$의 단조성 표현은 $<, >, =, <, >$이다.

단조성 표현이 $s_1, s_2, \ldots, s_n$인 수열이 또 다른 표현 $s'_1, s'_2, \ldots, s'_k$를 실현한다는 것은, 모든 $i = 1, 2, \ldots, n$에 대해 $s_i = s'_{((i-1) \bmod k) + 1}$이 성립함을 뜻한다. 다시 말해 $s_1, s_2, \ldots, s_n$은 $s'_1, s'_2, \ldots, s'_k$를 필요한 만큼 반복한 뒤 뒤쪽 일부를 잘라내어 얻을 수 있다. 예를 들어 $2, 4, 3, 3, 5, 3$은 $<, >, =$와 $<, >, =, <, >$, 그리고 $<, >, =, <, >, <, <, =$ 등 많은 표현을 실현한다.

정수 수열 $a_1, a_2, \ldots, a_n$과 단조성 표현 $s_1, s_2, \ldots, s_k$가 주어진다. 인덱스가 $1 \le i_1 < i_2 < \cdots < i_m \le n$인 부분 수열 $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ 중에서, 그 자신의 단조성 표현이 $s_1, s_2, \ldots, s_k$를 실현하는 것을 생각하자. 이러한 부분 수열의 최대 길이 $m$을 구하라. 원소가 하나뿐인 부분 수열은 (단조성 표현이 비어 있으므로) 항상 주어진 표현을 실현하므로, 답은 항상 $1$ 이상이다.

첫째 줄에 두 정수 $n$과 $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 500{,}000$, $1 \le k \le 500{,}000$). 각각 수열의 길이와 단조성 표현의 길이이다.

둘째 줄에 수열의 원소 $a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다 ($1 \le a_i \le 1{,}000{,}000$).

셋째 줄에 단조성 표현을 이루는 $k$개의 기호 $s_1, s_2, \ldots, s_k$가 공백으로 구분되어 주어진다. 각 기호는 $<$, $>$, $=$ 중 하나이다.

부분 수열 자신의 단조성 표현이 $s_1, s_2, \ldots, s_k$를 실현하는 부분 수열의 최대 길이 $m$을 정수 하나로 출력한다.