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 <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

int N, M;
int xs[100000];
int ys[100000];
int ix[2];
int jx[2];
int sgn(int x){
  return x / abs(x);
}

bool solve1(){
  if(ys[0] > ys[1])
	REP(i,N)
	  xs[i] *= -1;
  
  VI lis(N+1, 1e9);
  REP(i,N)
	*lower_bound(ALL(lis), xs[i]) = xs[i];
  int len = lower_bound(ALL(lis), 1e9) - begin(lis);
  return len >= M;
}
bool match(int xtop, int xlb, int xub, int ytop){
  int xl = xtop - 1, xr = xtop + 1;
  int px = xs[xtop];
  int yl = ytop - 1, yr = ytop + 1;
  REP(i,M-1){
	if(xl < xlb && xr > xub)
	  return false;
	int d = 0;
	if(yl < 0)
	  d = 1;
	else if(yr >= M)
	  d = -1;
	else
	  d = (ys[yl] > ys[yr]? -1: 1);
	
	if(d < 0){
	  while(xl >= xlb && xs[xl] >= px) --xl;
	  if(xl < xlb)
		return false;
	  px = xs[xl--];
	  --yl;
	}
	else{
	  while(xr <= xub && xs[xr] >= px) ++xr;
	  if(xr > xub) break;
	  px = xs[xr++];
	  ++yr;
	}
  }
  return (yl == -1 && yr == M);
}
bool solve2(){
  if(xs[0] > xs[ix[0]]){
	REP(i,N) xs[i] *= -1;
	REP(i,M) ys[i] *= -1;
  }

  if(ys[0] < ys[jx[0]]){
	return match(ix[0], 0, ix[1], jx[0]);
  }
  else{
	REP(i,N) xs[i] *= -1;
	REP(i,M) ys[i] *= -1;
	return match(ix[1], ix[0], N-1, jx[0]);
  }
}

bool solve3(){
  if(xs[0] > xs[ix[0]]){
	REP(i,N) xs[i] *= -1;
	REP(i,M) ys[i] *= -1;
  }
  if(ys[0] > ys[jx[0]])
	return false;

  int x1 = ix[0], x2 = x1+1, x3 = N-1;
  int y1 = jx[0], y2 = y1+1, y3 = M-1;
  int px = N+10;
  REP(i,M){
	if(x1 < 0 && ix[1] < x2 && x3 <= ix[2])
	  return false;
	int d;
	VI yys(3);
	yys[0] = (y1 < 0? -1e9: ys[y1]);
	yys[1] = (jx[1] < y2? -1e9: ys[y2]);
	yys[2] = (y3 <= jx[1]? -1e9: ys[y3]);

	if(yys[0] > yys[1] && yys[0] > yys[2])
	  d = -1;
	else if(yys[1] > yys[0] && yys[1] > yys[2])
	  d = 0;
	else
	  d = 1;
	
	if(d < 0){
	  while(x1 >= 0 && xs[x1] >= px) --x1;
	  if(x1 < 0)
		return false;
	  px = xs[x1--];
	  --y1;
	}
	else if(d == 0){
	  while(x2 <= ix[1] && xs[x2] >= px) ++x2;
	  if(x2 > ix[1])
		return false;
	  px = xs[x2++];
	  ++y2;
	}
	else{
	  while(x3 > ix[1] && xs[x3] >= px) --x3;
	  if(x3 <= ix[1])
		return false;
	  px = xs[x3--];
	  --y3;
	}
  }
  return (y1 == -1 && y2 == jx[1]+1 && y3 == jx[1]);
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  cin >> N;
  REP(i,N) cin >> xs[i];
  cin >> M;
  REP(i,M) cin >> ys[i];
  if(M == 1){
	cout << "Yes" << endl;
	return 0;
  }

  int run = 0, sg = sgn(xs[1] - xs[0]);
  for(int i=1;i<N;++i)
	if(sgn(xs[i] - xs[i-1]) != sg){
	  ix[run++] = i-1;
	  sg = sgn(xs[i] - xs[i-1]);
	}

  run = 1, sg = sgn(ys[1] - ys[0]);
  for(int i=1;i<M;++i)
	if(sgn(ys[i] - ys[i-1]) != sg){
	  jx[min(1,run-1)] = i-1;
	  sg = sgn(ys[i] - ys[i-1]);
	  ++run;
	}

  bool ans = false;
  if(run == 1)
	ans = solve1();
  else if(run == 2)
	ans = solve2();
  else if(run == 3)
	ans = solve3();

  cout << (ans? "Yes": "No") << endl;

  return 0;
}