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:
// need
#include <iostream>
#include <algorithm>

// data structure
#include <bitset>
//#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
//#include <array>
//#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <complex>
//#include <deque>
#include<valarray>

// stream
//#include <istream>
//#include <sstream>
//#include <ostream>

// etc
#include <cassert>
#include <functional>
#include <iomanip>
//#include <typeinfo>
#include <chrono>
#include <random>
#include <numeric>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC_ROW(type, n, ...)std::vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int i=0; i<n; ++i){MACRO_VEC_ROW_Scan(i, __VA_ARGS__);}
template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest&...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); }
template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest&...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); }
#define OUT(d) std::cout<<d;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d;
#define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d;
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
#define FORLL(i, a, b) for(ll i=ll(a);i<ll(b);++i)
#define RFORLL(i, a, b) for(ll i=ll(b)-1;i>=ll(a);--i)
#define REPLL(i, n) for(ll i=0;i<ll(n);++i)
#define RREPLL(i, n) for(ll i=ll(n)-1;i>=0;--i)
#define PAIR std::pair<int, int>
#define PAIRLL std::pair<ll, ll>
#define IN(a, x, b) (a<=x && x<b)
#define SHOW(d) {std::cerr << #d << "\t:" << d << "\n";}
#define SHOWVECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
#define SHOWPAIR(p) {std::cerr << #p << "\t:(" << p.first << ",\t" << p.second << ")\n";}
#define SHOWPAIRVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr<<'('<<yyy.first<<", "<<yyy.second<<") ";}std::cerr << "\n";}}
#define SHOWPAIRVECTOR(v) {for(const auto& xxx:v){std::cerr<<'('<<xxx.first<<", "<<xxx.second<<") ";}std::cerr<<"\n";}
#define SHOWQUEUE(a) {std::queue<decltype(a.front())> tmp(a);std::cerr << #a << "\t:";for(int i=0; i<static_cast<int>(a.size()); ++i){std::cerr << tmp.front() << "\n";tmp.pop();}std::cerr << "\n";}
template<typename T> inline T CHMAX(T& a, const T b) { return a = (a < b) ? b : a; }
template<typename T> inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; }
#define EXCEPTION(msg) throw std::string("Exception : " msg " [ in ") + __func__ + " : " + std::to_string(__LINE__) + " lines ]"
#define TRY(cond, msg) try {if (cond) EXCEPTION(msg);}catch (std::string s) {std::cerr << s << std::endl;}
void CHECKTIME(std::function<void()> f) { auto start = std::chrono::system_clock::now(); f(); auto end = std::chrono::system_clock::now(); auto res = std::chrono::duration_cast<std::chrono::nanoseconds>((end - start)).count(); std::cerr << "[Time:" << res << "ns  (" << res / (1.0e9) << "s)]\n"; }

//#define int ll
using ll = long long;
using ull = unsigned long long;
constexpr int INFINT = 1 << 30;                          // 1.07x10^ 9
constexpr int INFINT_LIM = (1LL << 31) - 1;              // 2.15x10^ 9
constexpr ll INFLL = 1LL << 60;                          // 1.15x10^18
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);  // 9.22x10^18
constexpr double EPS = 1e-7;
constexpr int MOD = 1000000007;
constexpr double PI = 3.141592653589793238462643383279;

signed main() {
	INIT;
	VAR(int, n);
	VEC(int, q, n);
	VAR(int, m);
	VEC(int, p, m);
	if (m == 1) {
		OUT("Yes")BR;
		return 0;
	}
	if (q[0] < q[1]) {
		int inc = 0;
		{
			std::vector<int> dp(n, INFINT);
			REP(i, n) {
				*std::lower_bound(ALL(dp), q[i]) = q[i];
			}
			inc = std::distance(dp.begin(), std::lower_bound(ALL(dp), INFINT));
		}
		int dec = 1;
		FOR(i, 1, n) {
			if (q[i - 1] > q[i]) ++dec;
		}
		int a = 1, b = 1;
		bool first = true;
		FOR(i, 1, n) {
			if (q[i - 1] < q[i]) {
				if (first) ++a;
				else ++b;
			}
			else {
				first = false;
			}
		}
		///
		int x = 1, y = 1, z = 1;
		first = true;
		FOR(i, 1, m) {
			if (p[i - 1] < p[i]) {
				if (first) ++x;
				else ++z;
			}
			else {
				if (z != 1) {
					OUT("No")BR;
					return 0;
				}
				first = false;
				++y;
			}
		}
		if (x != 1 && y == 1 && z == 1) { // up
			OUT(((inc >= x) ? "Yes" : "No"))BR;
		}
		else if (x == 1 && y != 1 && z == 1) { // down
			OUT(((dec >= y) ? "Yes" : "No"))BR;
		}
		else if (x != 1 && y != 1 && z == 1) { // up-down
			OUT(((a >= x && dec >= y) ? "Yes" : "No"))BR;
		}
		else if (x == 1 && y != 1 && z != 1) { // down-up
			OUT(((dec >= y && b >= z) ? "Yes" : "No"))BR;
		}
		else if (x != 1 && y != 1 && z != 1) { // up-down-up
			OUT(((a >= x && dec >= y && b >= z) ? "Yes" : "No"))BR;
		}
		else {
			assert(false);
		}
	}
	///////////////////////////////////////////////////////////////////////
	else {
		int min = INFINT;
		int dec = 0;
		{
			std::vector<int> dp(n, INFINT);
			REP(i, n) {
				*std::lower_bound(ALL(dp), -q[i]) = -q[i];
			}
			dec = std::distance(dp.begin(), std::lower_bound(ALL(dp), INFINT));
		}
		int inc = 1;
		FOR(i, 1, n) {
			if (q[i - 1] < q[i]) ++inc;
		}
		int a = 1, b = 1;
		bool first = true;
		FOR(i, 1, n) {
			if (q[i - 1] > q[i]) {
				if (first) ++a;
				else ++b;
			}
			else {
				first = false;
			}
		}
		///
		int x = 1, y = 1, z = 1;
		first = true;
		FOR(i, 1, m) {
			if (p[i - 1] > p[i]) {
				if (first) ++x;
				else ++z;
			}
			else {
				if (z != 1) {
					OUT("No")BR;
					return 0;
				}
				first = false;
				++y;
			}
		}
		if (x != 1 && y == 1 && z == 1) { // down
			OUT(((dec >= x) ? "Yes" : "No"))BR;
		}
		else if (x == 1 && y != 1 && z == 1) { // up
			OUT(((inc >= y) ? "Yes" : "No"))BR;
		}
		else if (x != 1 && y != 1 && z == 1) { // down-up
			OUT(((a >= x && inc >= y) ? "Yes" : "No"))BR;
		}
		else if (x == 1 && y != 1 && z != 1) { // up-down
			OUT(((inc >= y && b >= z) ? "Yes" : "No"))BR;
		}
		else if (x != 1 && y != 1 && z != 1) { // down-up-down
			OUT(((a >= x && inc >= y && b >= z) ? "Yes" : "No"))BR;
		}
		else {
			assert(false);
		}
	}
	return 0;
}