P1226

[Poi2010]Monotonicity

[Poi2010]Monotonicity

给定一个长度为 nn 的整数序列 aa，以及一个长度为 kk 的比较符号序列 ss，其中 si∈{<,>,=}s_i\in\{<,>,=\}。

请选择下标 1≤p1<p2<⋯<pm≤n1\le p_1<p_2<\cdots<p_m\le n，使得对于每个 t=1,2,…,m−1t=1,2,\ldots,m-1，apta_{p_t} 与 apt+1a_{p_{t+1}} 之间的关系满足符号 s((t−1) mod k)+1s_{((t-1)\bmod k)+1}：

  • 当符号为 << 时，要求 apt<apt+1a_{p_t}<a_{p_{t+1}}；
  • 当符号为 >> 时，要求 apt>apt+1a_{p_t}>a_{p_{t+1}}；
  • 当符号为 == 时，要求 apt=apt+1a_{p_t}=a_{p_{t+1}}。

也就是说，比较符号将按照 s1,s2,…,sk,s1,s2,…s_1,s_2,\ldots,s_k,s_1,s_2,\ldots 的顺序循环使用。

求满足条件的子序列的最大长度 mm。当 m=1m=1 时，不需要满足任何相邻元素之间的关系。

输入格式

第一行包含两个正整数 nn 和 kk。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行包含 kk 个比较符号 s1,s2,…,sks_1,s_2,\ldots,s_k，符号之间可以用空白字符分隔。每个符号均为 <<、>> 或 ==。

输出格式

输出一个整数，表示满足条件的最长子序列的长度。

样例输入

7 3
2 4 3 1 3 5 3
= = =

样例输出

3

样例解释

可以选择序列中三个值为 33 的元素。相邻元素之间的关系均为 ==，因此满足给定的关系序列，最长子序列长度为 33。

数据范围

  • 1≤n≤2×1041\le n\le 2\times 10^4；
  • 1≤k≤1001\le k\le 100；
  • 1≤ai≤1061\le a_i\le 10^6。

来源与许可

本题为 POI 2010 试题「Monotonicity」，题面与测试数据整理自 BZOJ。

样例 1

输入

7 3
2 4 3 1 3 5 3
= = =

输出

3