[Poi2010]Monotonicity 2

内存限制：259 MiB 时间限制：30 Sec

提交提交记录讨论

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

一个正整数，表示L的最大值。

样例输入


			7 3

2 4 3 1 3 5 3

< > =

样例输出

选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。