Love Permutation, Run run run!

Time Limit : 1 sec, Memory Limit : 262142 KB

G: 恋のジュンレツRun!Run!Run! - Love Permutation, Run run run! -

物語

おおきなジュンレツ らんらんらんでぶー♪ Hello, 星空蘭にゃ! 好きなデータ構造は Starry Sky Tree にゃ!

蘭は最近物理学科に入学したんだけど、どうやらそこでもプログラミングをやらないといけないらしいんだ。 蘭、アルゴリズムやデータ構造の理論は好きなんだけど、実装はどうも苦手なんだよね…… だいたい蘭達は人間なのに、どうして機械の言葉を勉強しなくちゃいけないの!?

とはいえ、課題をやらないことには単位が出ないしやるしかないにゃ。 今回出た課題は順列の run とかいうのが関係しているらしいんだー。 この問題、明らかに作者がタイトル一発ネタで考えてるのが見え見えにゃ、ちょっと寒くないかにゃー。 とにかく、プログラミングが得意なあなたに手伝ってもらえたら、テンション上がるにゃー! それじゃあ問題、行っくにゃ〜!

問題

長さKの数列a1 \leq a_i \leq K (1 \leq i \leq K) かつa_i \neq a_j (1 \leq i < j \leq K) を満たすとき、aは長さKの順列であるという。

ここで順列のパターンマッチングを以下のように定義する。 テキスト順列qがパターン順列pにマッチするとは、pと相対順序が一致するような、pと同じ長さのqの (連続とは限らない) 部分列が存在することをいう。 より厳密には、qの長さをNpの長さをMとしたとき、qpにマッチするとは、ある条件を満たす添え字列 1 \leq i_1 < ... < i_M \leq Nが存在することである。その条件とは、p_x < p_y (1 \leq x<y \leq M) ならば、かつそのときに限りq_{i_x} < q_{i_y}となることである。 例えば、順列(3, 4, 2, 1, 5)は順列(2, 1, 3)にマッチする。なぜならば、添え字列(1, 4, 5)が上記の条件を満たすからである。

さらに、順列の run を定義する。 順列のrunとは、単調増加、あるいは単調減少な極大連続部分列である。すなわち、run は連続部分列 a_l, ..., , a_r (l<r) のうち、a_i < a_{i+1} (l \leq i < r) (a_i > a_{i+1} (l \leq i < r)) を満たし、かつこの区間を真に包含する連続区間からなる run が存在しないものを言う。 例えば、順列(3, 4, 2, 1, 5)(3, 4), (4, 2, 1), (1, 5)という3つのrunを持つ。

長さNのテキスト順列qと長さMのパターン順列pが与えられる。 ここで、qは必ずちょうど3つだけの run を持つことが保証される。 qpにマッチするかどうかを判定せよ。

入力形式

入力は以下の形式で与えられる。

N
q_1 ... q_N
M
p_1 ... p_M

入力は全て整数からなる。 1行目にはテキストとなる順列qの長さNが与えられる。 続く2行目はN個の整数が空白区切りで与えられ、i (1 \leq i \leq N) 番目の整数はqi番目の要素q_iを表す。 3行目にはパターンとなる順列pの長さMが与えられる。 続く4行目はM個の整数が空白区切りで与えられ、j (1 \leq j \leq M) 番目の整数はpj番目の要素p_jを表す。

制約

  • 4 \leq N \leq 10^5
  • 1 \leq M \leq N
  • q, pはそれぞれ長さN, Mの順列である。
  • qが持つ run の数はちょうど3。

出力形式

順列qが順列pにマッチするとき"Yes"、そうでなければ"No"と1行に出力せよ。

入力例1

5
3 4 2 1 5
3
1 2 3

出力例1

Yes

入力例2

5
3 5 4 1 2
3
1 2 3

出力例2

No

Source: Ritsumeikan University Programming Camp 2017 , Day 3, Shiga, Japan, 2017-03-24