Monotonicity 2

Monotonicity 2

暂无测试数据。

题目描述

给出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个正整数表示ai
第三行给出K个空格隔开关系符号(>、<或=),第i个表示s[i]。

输出格式

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

样例输入

7 3
2 4 3 1 3 5 3
< > =

样例输出

6

提示

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

信息

难度
10
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
上传者