F

void solve() {
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for(int i = 0;i < n; i ++){
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a.begin(), a.end());
    int ans = 0, l = n, r = -1;
    for(int i = 0;i < n; i++){
        l = min(l, a[i].second);
        r = max(r, a[i].second);
        if(a[i].first == r - l + 1) ans ++;
    }
    cout << ans << "\n";
}

G

void solve() {
    int n; cin >> n;
    vector<vector<int>> adj(n+1);
    for(int i = 1;i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> p(n+1);
    vector<bool> vis(n+1);
    for(int i = 1;i <= n; i++) cin >> p[i];
    int ans = 0, x = p[1], y = p[1], z = p[1];//z表示上一个路径的最后一个结点,x表示z的父节点，y表示上一条路径的另一端最外面的结点，
    vis[p[1]] = true;
    function<void(int, int, int)> dfs = [&](int v, int parent, int flag){
        if(ans > n) return ;//不会超过n个点
        if(vis[p[ans]]) return ;//访问过的直接退出，实际上好像不会遇到这种情况吧？
        if(p[ans] == v){//找到目标节点的位置p[ans],这里的ans其实等价于外面的i，p[ans]=p[i]
            vis[v] = true;//找到了就标记
            vis[parent] = true;//路径的过程也标记
            if(flag == 0)//更新链尾的父节点,flag=1的话就是链首了，我们不管他，让他的链首的父节点等于他本身
            x = parent;
            return ;
        }
        for(auto &u : adj[v]){
            if(u != parent){
                if(!vis[u]) dfs(u, v, flag);//没访问过的点继续访问，知道找出目标节点p[i],也就是p[ans]
            }
        }
        if(vis[v]) vis[parent] = true;//和上面一样，将最短路径的所有点都进行标记
    };
    bool ok = true;
    for(int i = 1;i <= n; i++){
        ans ++;
        if(vis[p[i]]) continue;//标记过的点说明在之前的路径上，跳过
        dfs(z, x, 0);//继续从上一条路径的末端继续遍历查询p[i]的点是否存在
        if(vis[p[i]]) z = p[i];//存在就更新上一条路径的链尾
        if(!vis[p[i]]){
            dfs(y, y, 1);//不存在就对链首遍历
            y = p[i];//有的话就更新链首
        }
        if(!vis[p[i]]){//没有的话后面也不会有了，直接退出
            ok = false;//减去当前循环的多加的一个1
            break;
        }
    }
    if(!ok) ans --;
    cout << ans << "\n";
    /*时间复杂度也算是相当于O(n)了吧,标记过的点就不访问了*/
}