P3506 [POI 2010] MOT-Monotonicity 2

本题是来自 POI 2010 第三阶段的[单调性](https://www.luogu.com.cn/problem/P3541)一题的加强版，但并没有在那次比赛中被使用。 **译自 POI 2010 「[Monotonicity 2](https://szkopul.edu.pl/problemset/problem/0_pcwjQ6no8LDss0IWNLbb2_/site/?key=statement)」** 对于一个整数序列 $a_1, a_2, ..., a_n$，我们定义其“单调序列"为一个由 $$ 和 $=$ 组成的符号序列 $s_1, s_2, ... s_{n-1}$，其中符号 $s_i$ 表示 $a_i$ 和 $a_{i+1}$ 之间的关系。例如，数列 $2, 4, 3, 3, 5, 3$ 的单调序列为 $, =, $。 对于整数序列 $b_1, b_2, ..., b_{n+1}$ 以及其单调序列 $s_1, s_2, ..., s_n$，如果符号序列 $s_1', s_2', ..., s_k'$ 满足对所有 $1 \le i \le n$ 有 $s_i = s_{((i - 1) \bmod n) + 1}'$，我们就说序列 $s_1, s_2, ..., s_n$ 「实现」了序列 $s_1', s_2', ..., s_k'$。也就是说，序列 $s_1, s_2, ..., s_n$ 可以通过重复多次 $s_1', s_2', ..., s_k'$ 序列并删除一个后缀得到。例如，整数数列 $2, 4, 3, 3, 5, 3$ 至少实现了以下符号序列： * $, =$ * $, =, $ * $, =, , $ 给定一个整数序列 $a_1, a_2, ..., a_n$ 以及一个单调序列 $s_1, s_2, ..., s_k$，求出原整数序列最长的子序列 $a_{i_1}, a_{i_2}, ..., a_{i_m} (1 \le i_1 \lt i_2 \lt ... \lt i_m \le n)$ 使得前者的单调序列实现后者的符号序列。

无

无

对于 $100\%$ 的数据， $1 \le n \le 500000,1 \le k \le 500000 , 1 \le a_i \le 1000000 , s_j \in \{, =\}$ 。 感谢 [本帖](https://www.luogu.com.cn/discuss/67056) 提供的 SPJ。翻译来自于 [LibreOJ](https://loj.ac/p/3009)。