Problem: G: Koi no Junretsu Run! Run! Run! --Love Permutation, Run run run! -

story

Big Junretsu Ranran Randebu ♪ Hello, Hoshizora Ran Nya! My favorite data structure is Starry Sky Tree Nya!

Ran recently enrolled in the Department of Physics, but apparently he has to do programming there as well. Orchids, I like the theory of algorithms and data structures, but I'm not very good at implementing them ... Mostly, orchids are humans, but why do I have to study the language of machines! ??

However, if you don't do the task, you have to do it without getting credit. It seems that the issue that came out this time is related to the permutation run. If you can't see the author thinking about this problem with a single title, it's a little cold. Anyway, if you are good at programming and help me, I'll get excited! Then the problem is, let's go!

problem

If the sequence a of length K satisfies 1 \ leq a_i \ leq K (1 \ leq i \ leq K) and a_i \ neq a_j (1 \ leq i <j \ leq K), then a is a permutation of length K. It is said that.

Here, permutation pattern matching is defined as follows. A text permutation q matches a pattern permutation p means that there is a (not necessarily continuous) subsequence of q of the same length as p, such that the relative order matches p. Strictly speaking, when the length of q is N and the length of p is M, the fact that q matches p is a subscript string 1 \ leq i_1 <... <i_M \ leq N that satisfies a certain condition. Is to exist. The condition is that p_x <p_y (1 \ leq x <y \ leq M), and only then q_ {i_x} <q_ {i_y}. For example, a permutation (3, 4, 2, 1, 5) matches a permutation (2, 1, 3). This is because the subscript strings (1, 4, 5) satisfy the above conditions.

In addition, define a permutation run. A permutation run is a maximal continuous subsequence that is monotonically increasing or monotonically decreasing. That is, run is a continuous subsequence a_l, ...,, a_r (l <r), a_i <a_ {i + 1} (l \ leq i <r) (a_i> a_ {i + 1} (l) It means that there is no run consisting of continuous intervals that satisfy \ leq i <r)) and truly include this interval. For example, a permutation (3, 4, 2, 1, 5) has three runs: (3, 4), (4, 2, 1), (1, 5).

Given a text permutation q of length N and a pattern permutation p of length M. Here, q is guaranteed to always have exactly three runs. Determine if q matches p.

Input format

The input is given in the following format.


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


All inputs consist of integers. The first line is given the length N of the permutation q, which is the text. The second line that follows is given N integers separated by blanks, and the i (1 \ leq i \ leq N) th integer represents the i-th element q_i of q. The third row is given the length M of the permutation p, which is the pattern. In the following 4th line, M integers are given separated by blanks, and the j (1 \ leq j \ leq M) th integer represents the jth element p_j of p.

Constraint

* 4 \ leq N \ leq 10 ^ 5
* 1 \ leq M \ leq N
* q and p are permutations of length N and M, respectively.
* q has exactly 3 runs.



Output format

Print "Yes" if permutation q matches permutation p, otherwise "No" on one line.

Input example 1


Five
3 4 2 1 5
3
one two Three


Output example 1


Yes

Input example 2


Five
3 5 4 1 2
3
one two Three


Output example 2


No





Example

Input

5
3 4 2 1 5
3
1 2 3


Output

Yes

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define INF 10000000
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
int q[100001],p[100001];
bool flag;
int dp[100001][2];
vector<int> g[3];
vector<int> pg[3];
int dp2[100001];
bool checked[2][100001];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&q[i]);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&p[i]);
	}
	if(p[0]>p[1])flag=true;
	else flag=false;
	int cnt=1;
	for(int i=1;i<m-1;i++){
		bool next=false;
		if(p[i]>p[i+1])next=true;
		if(next!=flag)cnt++;
		flag=next;
	}
	if(cnt>3){
		printf("No\n");
		return 0;
	}else if(cnt==1){
		if(p[0]<p[1]){
			fill(dp2,dp2+n,INF);
			for(int i=0;i<n;i++){
				*lower_bound(dp2,dp2+n,q[i])=q[i];
			}
			int val=lower_bound(dp2,dp2+n,INF)-dp2;
			printf("%s\n",val>=m?"Yes":"No");
		}else{
			fill(dp2,dp2+n,INF);
			for(int i=0;i<n;i++){
				*lower_bound(dp2,dp2+n,INF-1-q[i])=INF-1-q[i];
			}
			int val=lower_bound(dp2,dp2+n,INF)-dp2;
			printf("%s\n",val>=m?"Yes":"No");
		}
	}else if(cnt==2){
		g[0].push_back(q[0]);
		g[0].push_back(q[1]);
		bool qdown=false;
		flag=false;
		if(q[0]>q[1]){
			qdown=true;
			flag=true;
		}
		int nc=0;
		for(int i=1;i<n-1;i++){
			bool next=false;
			if(q[i]>q[i+1])next=true;
			if(next==flag){
				g[nc].push_back(q[i+1]);
			}else{
				nc++;
				g[nc].push_back(q[i]);
				g[nc].push_back(q[i+1]);
			}
			flag=next;
		}

		pg[0].push_back(p[0]);
		pg[0].push_back(p[1]);
		bool pdown=false;
		flag=false;
		if(p[0]>p[1]){
			pdown=true;
			flag=true;
		}
		nc=0;
		for(int i=1;i<m-1;i++){
			bool next=false;
			if(p[i]>p[i+1])next=true;
			if(next==flag){
				pg[nc].push_back(p[i+1]);
			}else{
				nc++;
				pg[nc].push_back(p[i]);
				pg[nc].push_back(p[i+1]);
			}
			flag=next;
		}
		flag=false;
		int side=0;
		if(pdown!=qdown)side=1;
		sort(pg[0].begin(),pg[0].end());
		sort(pg[1].begin(),pg[1].end());
		sort(g[side].begin(),g[side].end());
		sort(g[1+side].begin(),g[1+side].end());
		int ql1=0,ql2=0,pl1=0,pl2=0;
		int nval=-1;
		memset(checked,false,sizeof(checked));
		while(pl1<pg[0].size() || pl2<pg[1].size()){
			int val=-1,which=-1;
			if(pl1==pg[0].size())val=pg[1][pl2],which=1;
			else if(pl2==pg[1].size())val=pg[0][pl1],which=0;
			else{
				if(pg[0][pl1]<pg[1][pl2]){
					val=pg[0][pl1];
					which=0;
				}else{
					val=pg[1][pl2];
					which=1;
				}
			}
			if(!checked[1][val]){
				checked[1][val]=true;
				if(which==0){
					while(1){
						if(ql1==g[side].size()){
							printf("No\n");
							return 0;
						}
						int val2=g[side][ql1];
						if(nval<val2 && !checked[0][val2]){
							nval=val2;
							checked[0][val2]=true;
							break;
						}
						ql1++;
					}
				}else{
					while(1){
						if(ql2==g[side+1].size()){
							printf("No\n");
							return 0;
						}
						int val2=g[side+1][ql2];
						if(nval<val2 && !checked[0][val2]){
							nval=val2;
							checked[0][val2]=true;
							break;
						}
						ql2++;
					}
				}
			}
			if(which==0)pl1++;
			else pl2++;
		}
		printf("Yes\n");
		return 0;
	}else if(cnt==3){
		g[0].push_back(q[0]);
		g[0].push_back(q[1]);
		bool qdown=false;
		flag=false;
		if(q[0]>q[1]){
			qdown=true;
			flag=true;
		}
		int nc=0;
		for(int i=1;i<n-1;i++){
			bool next=false;
			if(q[i]>q[i+1])next=true;
			if(next==flag){
				g[nc].push_back(q[i+1]);
			}else{
				nc++;
				g[nc].push_back(q[i]);
				g[nc].push_back(q[i+1]);
			}
			flag=next;
		}

		pg[0].push_back(p[0]);
		pg[0].push_back(p[1]);
		bool pdown=false;
		flag=false;
		if(p[0]>p[1]){
			pdown=true;
			flag=true;
		}
		nc=0;
		for(int i=1;i<m-1;i++){
			bool next=false;
			if(p[i]>p[i+1])next=true;
			if(next==flag){
				pg[nc].push_back(p[i+1]);
			}else{
				nc++;
				pg[nc].push_back(p[i]);
				pg[nc].push_back(p[i+1]);
			}
			flag=next;
		}
		flag=false;
		if(pdown!=qdown){
			printf("No\n");
			return 0;
		}

		for(int i=0;i<3;i++){
			sort(pg[i].begin(),pg[i].end());
			sort(g[i].begin(),g[i].end());
		}
		int ql[3],pl[3];
		int nval=-1;
		memset(ql,0,sizeof(ql));
		memset(pl,0,sizeof(pl));
		memset(checked,false,sizeof(checked));
		while(pl[0]<pg[0].size() || pl[1]<pg[1].size() || pl[2]<pg[2].size()){
			int val=11451419,which=-1;
			int valc[3];
			for(int i=0;i<3;i++){
				if(pl[i]!=pg[i].size())valc[i]=pg[i][pl[i]];
				else valc[i]=11451419;
			}
			for(int i=0;i<3;i++){
				if(val>valc[i]){
					val=valc[i];
					which=i;
				}
			}
			if(!checked[1][val]){
				checked[1][val]=true;
				while(1){
					if(ql[which]==g[which].size()){
						printf("No\n");
						return 0;
					}
					int val2=g[which][ql[which]];
					if(nval<val2 && !checked[0][val2]){
						nval=val2;
						checked[0][val2]=true;
						break;
					}
					ql[which]++;
				}
			}
			pl[which]++;
		}
		printf("Yes\n");
		return 0;
	}
	return 0;
}