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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int UP = 1, DOWN = 0;
const int INF = 1 << 30;
int n, m;

vector<int> inv(vector<int> a) {
    int sz = a.size();
    vector<int> ret(sz);
    for(int i=0; i<sz; i++) ret[i] = sz - a[i] + 1;
    return ret;
}

vector<pii> getrun(vector<int> a) {
    vector<pii> ret;
    if(a.size() == 1) {
        ret.push_back(pii(0, UP));
        return ret;
    }

    if(a[0] < a[1]) ret.push_back(pii(0, UP  ));
    if(a[0] > a[1]) ret.push_back(pii(0, DOWN));

    for(size_t i=1; i<a.size()-1; i++) {
        if(a[i-1] < a[i] && a[i] > a[i+1])
            ret.push_back(pii(i, DOWN));
        if(a[i-1] > a[i] && a[i] < a[i+1])
            ret.push_back(pii(i, UP  ));
    }
    return ret;
}

pii getedge(vector<int> a, vector<pii> run) {
    int n = a.size();
    int x = run[1].first, y = run[2].first;
    int ret_a = upper_bound(a.begin(), a.begin()+x, a[y]) - a.begin();
    int ret_b = upper_bound(a.begin()+y, a.begin()+n, a[x]) - a.begin();
    ret_b = n - ret_b;
    return pii(ret_a, ret_b);
}

int solve_1(vector<int> a) {
    int x = a.size(), ret = 0;
    vector<int> temp(x, (int)1e9);
    for(int i=0; i<x; i++) {
        int idx = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin();
        temp[ idx ] = a[i];
        ret = max(ret, idx+1);
    }
    return ret;
}

bool solve_2(vector<int> p, vector<int> q, vector<pii> run_p, vector<pii> run_q) {
    int stp, stq;
    run_p.push_back(pii(INF, -1));
    run_q.push_back(pii(INF, -1));
    for(size_t i=1; i<run_p.size(); i++) {
        if(run_p[i].second == DOWN) stp = i;
    }
    for(size_t i=1; i<run_q.size(); i++) {
        if(run_q[i].second == DOWN) stq = i;
    }
    vector<pii> vp, vq;
    int x1 = run_p[stp].first + 1, x2 = run_p[stp].first - 1;
    int y1 = run_q[stq].first + 1, y2 = run_q[stq].first - 1;
    while(x1 <= min((int)p.size()-1, run_p[stp+1].first))
        vp.push_back(pii(p[x1++], 0));
    while(x2 >= max(0              , run_p[stp-1].first))
        vp.push_back(pii(p[x2--], 1));
    while(y1 <= min((int)q.size()-1, run_q[stq+1].first))
        vq.push_back(pii(q[y1++], 0));
    while(y2 >= max(0              , run_q[stq-1].first))
        vq.push_back(pii(q[y2--], 1));
    sort(vp.begin(), vp.end(), greater<pii>());
    sort(vq.begin(), vq.end(), greater<pii>());

    int cur = 0, prev = (int)1e9;
    for(size_t i=0; i<vp.size(); i++) {
        int type = vp[i].second;
        while(1) {
            if(vq[cur].second == type && vq[cur].first < prev) {
                prev = vq[cur++].first;
                break;
            }
            if(++cur >= (int)vq.size()) return false;
        }
    }
    return true;
}

bool solve_3(vector<int> p, vector<int> q, vector<pii> run_p, vector<pii> run_q) {
    int n = q.size(), m = p.size();
    vector<pii> vp, vq;
    run_p.push_back(pii(INF, -1));
    run_q.push_back(pii(INF, -1));

    int i = 0, j = 1;
    while(i < n && j <= 3) {
        if(i < run_q[j].first) vq.push_back(pii(q[i], j-1));
        else if(i == run_q[j].first) j++;
        i++;
    }
    i = 0, j = 1;
    while(i < m && j <= 3) {
        if(i < run_p[j].first) vp.push_back(pii(p[i], j-1));
        else if(i == run_p[j].first) j++;
        i++;
    }
    sort(vp.begin(), vp.end(), greater<pii>());
    sort(vq.begin(), vq.end(), greater<pii>());

    int cur = 0, prev = (int)1e9;
    for(size_t i=0; i<vp.size(); i++) {
        int type = vp[i].second;
        while(1) {
            if(vq[cur].second == type && vq[cur].first < prev) {
                prev = vq[cur++].first;
                break;
            }
            if(++cur >= (int)vq.size()) return false;
        }
    }
    return true;
}

int main() {
    cin >> n;
    vector<int> q(n);
    for(int i=0; i<n; i++) cin >> q[i];

    cin >> m;
    vector<int> pat(m);
    for(int i=0; i<m; i++) cin >> pat[i];

    if(m > 1 && pat[0] > pat[1]) {
        q   = inv(q  );
        pat = inv(pat);
    }

    vector<pii> run_q   = getrun(q  );
    vector<pii> run_pat = getrun(pat);

    int pat_sz = run_pat.size(), flag = pat.size();
    if(pat_sz > (int)run_q.size()) {
        cout << "No" << endl;
    }
    else if(pat_sz == 1) {
        int l = solve_1(q);
        if(l >= flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else if(pat_sz == 2) {
        // pat ??????????±±??¢??§??????
        if(solve_2(pat, q, run_pat, run_q)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else if(pat_sz == 3) {
        // pat ????????? ?±± -> ?°? ??§??????
        if(run_q[1].second == DOWN) {
            pii eq = getedge(q, run_q);
            pii ep = getedge(pat, run_pat);
            if(eq.first < ep.first || eq.second < ep.second) cout << "No" << endl;
            else {
                if(solve_3(pat, q, run_pat, run_q)) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
        }
        else cout << "No" << endl;
    }
    else cout << "No" << endl;
    return 0;
}