Submission #69539718

---

Source Code Expand

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef __gnu_pbds::tree<int, __gnu_pbds::null_type,
less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define sa(a) int(a.size())
#define all(a) (a.begin()),(a.end())
#define zero(a) memset(a,0,sizeof(a))
#define fix(n) cout<<fixed<<setprecision(n)
#define vi vector<int>
#define vvi vector <vector<int> >
#define vl vector<ll>
#define vvl vector <vector<ll> >
#define rep(a,b,c,d) for(int a=b;a<c;a+=d)
#define rev(a,b,c,d) for(int a=b-1;a>=c;a-=d)

const long long MOD=998244353;
const long long MOD7=(ll)1e9+7;
const int INF= (int)1e9;
const ll LINF=(ll)1e18;
const ull ULINF=(ull)2e18;
vector <pair<int,int> > dxy={{-1,0},{0,1},{0,-1},{1,0}};

class DisjointSets {
  private:
  vector<int> parents;
  vector<int> sizes;

  public:
  DisjointSets(int size) : parents(size), sizes(size, 1) {
    for (int i = 0; i < size; i++) { parents[i] = i; }
  }

  int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

  bool unite(int x, int y) {
    int x_root = find(x);
    int y_root = find(y);
    if (x_root == y_root) { return false; }

    if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
    sizes[x_root] += sizes[y_root];
    parents[y_root] = x_root;
    return true;
  }
};



ll GCD(ll a, ll b){
    a=llabs(a),b=llabs(b);
    if (b==0)return a;
    if (a==0)return b;
    return GCD(b,a%b);
}

bool chk_dbl_eql(double x, double y, double ep){

    double a=fabs(x-y);
    double mx=max(x,y);
    return a<=mx*ep;
}
int popcount(long long N)
{
	int ans = 0;
	while (N > 0) {
		ans++;
		N ^= (N & -N);
	}
	return ans;
}

ll fast_pow(ll x, ll y){
    ll res=1;
    while(y){
        if (y&1){res*=x;}
        x*=x;
        y>>=1;
    }
    return res;

}

vector <ll> last_prime,primes;
void seive(ll M){

    last_prime.resize(M+1);

  for (ll i=2;i<=M;i++){
        if (last_prime[i]==0){
            primes.pb(i);
            last_prime[i]=i;
            for (ll j=i+i;j<=M;j+=i){
                last_prime[j]=i;
            }
        }
  }

}

long long modpow(long long x,long long y,long long n)
{
    long long res=1;
    while(y>0)
    {
        if (y&1)
        {
            res=((res%n)*(x%n))%n;
        }
        x=((x%n)*(x%n))%n;
        y/=2;
    }
    return res;
}
long long modmul(long long x,long long y,long long m)
{
    return ((x%m)*(y%m))%m;
}

ll modinv ( ll n, ll Mod )
{
    return modpow ( n, Mod - 2, Mod ) ;
}

ll moddiv(ll x, ll y, ll m)
{
    return modmul(x,modinv(y,m),m);
}


vector <ll> inv,fact;
void factorial(int N, ll m){
    fact.resize(N);
    fact[0]=1ll;
    for (ll i=1; i<N; i++)
    {
        fact[i]=(fact[i-1]*i)%m;
    }

}

void invfact(int N, ll m){
    inv.resize(N);
    inv[N-1]=modinv(fact[N-1],m);
    for (ll i=N-2;i>=0;i--){
        inv[i]=(inv[i+1]*(i+1))%m;
    }


}
ll ncr(long long n,long long r, long long m){

    if (r>n)return 0ll;
    else if (r==n)return 1ll;
    return (fact[n]*inv[r]%m*inv[n-r])%m;
}

ll invnum=0;
int invarr[(int)1e5+5];
void mergesort(int l, int r, int n, vector <int>& a){
     int m=(l+r)/2;
    if (l!=r){
    mergesort(l,m,n,a);
    mergesort(m+1,r,n,a);
    }
    else return ;
    int i=l,j=m+1;
    int k=l;
    while(i<=m && j<=r){
        if (a[i]>a[j]){
            invnum+=(1ll*m-1ll*i+1ll);
            invarr[k]=a[j];
            j++;
        }
        else {

            invarr[k]=a[i];
            i++;
        }
        k++;
    }
    while(i<=m){
        invarr[k]=a[i];
        k++;
        i++;
    }
    while(j<=r){
        invarr[k]=a[j];
        k++;
        j++;
    }

    for (int i=l;i<=r;i++)a[i]=invarr[i];

}

//GeeksforGeeks inversion count merge sort

int countAndMerge(vector<int>& arr, int l, int m, int r) {

    int n1 = m - l + 1, n2 = r - m;

    vector<int> left(n1), right(n2);
    for (int i = 0; i < n1; i++)
        left[i] = arr[i + l];
    for (int j = 0; j < n2; j++)
        right[j] = arr[m + 1 + j];

    int res = 0;
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {

        if (left[i] <= right[j])
            arr[k++] = left[i++];

        else {
            arr[k++] = right[j++];
            res += (n1 - i);
        }
    }

    while (i < n1)
        arr[k++] = left[i++];
    while (j < n2)
        arr[k++] = right[j++];

    return res;
}

int countInv(vector<int>& arr, int l, int r){
    int res = 0;
    if (l < r) {
        int m = (r + l) / 2;


        res += countInv(arr, l, m);
        res += countInv(arr, m + 1, r);

        res += countAndMerge(arr, l, m, r);
    }
    return res;
}

int inversionCount(vector<int> &arr) {
  	int n = arr.size();
  	return countInv(arr, 0, n-1);
}

void is(bool ok){
    if (ok)
        cout<<"Yes";
    else cout<<"No";
}


class segtreemn{

    private:
        vector <pair<ll,ll> > seg;

    public:
        segtreemn(int size): seg(4*size){
            for (int i=0;i<4*size;i++){
                seg[i]={2e9,i};
            }
        }

        void add(int ind , int l, int r, ll i,ll val){
            if (l==r){
                seg[ind]={val,-i};
                return;
            }
            int m=(r+l)/2;
            if (m>=i)
                add(ind*2,l,m,i,val);
            else
                add(ind*2+1,m+1,r,i,val);
            seg[ind]=min(seg[ind*2],seg[ind*2+1]);
        }

        pair<int,int> getmn(int ind, int l, int r,int st, int ed){
            if (l>ed || r<st)
                return {2e9,2e9};
            if (l>=st && r<=ed)
                return seg[ind];
            int m=(l+r)/2;
            return min(getmn(ind*2,l,m,st,ed),getmn(ind*2+1,m+1,r,st,ed));
        }
};

class segtreesum{

    private:
        vector <ll > seg;

    public:
        segtreesum(int size): seg(4*size,0ll){

        }

        int bisearch(int ind, int l, int r, ll val){
            if (l==r){
                return l;
            }
            int m=(l+r)/2;
            if (seg[ind*2]>=val)
                return bisearch(ind*2,l,m,val);
            val-=seg[ind*2];
            return bisearch(ind*2+1,m+1,r,val);
        }

        ll getnum(int ind, int l, int r, int i){
            if (l==r){
                return seg[ind];
            }
            int m=(l+r)/2;
            if (m>=i)
                return getnum(ind*2,l,m,i);
            return getnum(ind*2+1,m+1,r,i);
        }

        void add(int ind , int l, int r, ll i,ll val){
            if (l==r){
                seg[ind]=val;
                return;
            }
            int m=(r+l)/2;
            if (m>=i)
                add(ind*2,l,m,i,val);
            else
                add(ind*2+1,m+1,r,i,val);
            seg[ind]=seg[ind*2]+seg[ind*2+1];
        }

        ll getsum(int ind, int l, int r,int st, int ed){
            if (l>ed || r<st)
                return 0ll;
            if (l>=st && r<=ed)
                return seg[ind];
            int m=(l+r)/2;
            return getsum(ind*2,l,m,st,ed)+getsum(ind*2+1,m+1,r,st,ed);
        }
};

int ullpopcount(ull x){
    int ans=0;
    while(x){
        if (x&1)
            ans++;
        x>>=1;
    }
    return ans;
}




vector<int> manacher(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = min(r - i, p[l + (r - i)]);
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}


//int n;
//vector<vector<int>> adj(200005);
//vector<char> color;
//vector<int> parent;
//int cycle_start, cycle_end;
//
//bool dfs(int v) {
//    color[v] = 1;
//    for (int u : adj[v]) {
//        if (color[u] == 0) {
//            parent[u] = v;
//            if (dfs(u))
//                return true;
//        } else if (color[u] == 1) {
//            cycle_end = v;
//            cycle_start = u;
//            return true;
//        }
//    }
//    color[v] = 2;
//    return false;
//}
//
//bool find_cycle() {
//    color.assign(n, 0);
//    parent.assign(n, -1);
//    cycle_start = -1;
//
//    for (int v = 0; v < n; v++) {
//        if (color[v] == 0 && dfs(v))
//            break;
//    }
//
//    if (cycle_start == -1) {
//        return false;
//    } else {
//        return true;
//    }
//}
//
//vector<bool> visited;
//vector<int> ans;
//vector <int> dis;
//
//void dfs2(int v) {
//    visited[v] = true;
//    for (int u : adj[v]) {
//        if (!visited[u]) {
//            dfs2(u);
//        }
//    }
//    ans.push_back(v);
//}
//
//void topological_sort() {
//    visited.assign(n, false);
//    ans.clear();
//    dis.assign(n,0);
//    for (int i = 0; i < n; ++i) {
//        if (!visited[i]) {
//            dfs2(i);
//        }
//    }
//    reverse(ans.begin(), ans.end());
//}

class dsu{

    private:
        vector <int> parent,sizes,black,color;

    public:
        dsu(int size) : parent(size),sizes(size,1),black(size,0),color(size,0){
            for (int i=0;i<size;i++){
                parent[i]=i;
            }
        }
        int find(int x){return parent[x]==x?x:(parent[x]=find(parent[x]));}

        int getsize(int x){return sizes[x];}

        void flip(int x){
            color[x]=(!color[x]);
            if (color[x]){
                int y=find(x);
                black[y]++;
            }
            else {
                int y=find(x);
                black[y]--;
            }
        }

        bool isblack(int x){
            int y=find(x);
            if (black[y])
                return true;
            return false;
        }

        bool unite(int x, int y){

            x=find(x),y=find(y);
            if (x==y)
                return false;
            if (sizes[x]<sizes[y])
                swap(x,y);
            sizes[x]+=sizes[y];
            black[x]+=black[y];
            parent[y]=x;
            return true;
        }
};
class lazysum{
    private:
        vector <ll> seg;
        vector <ll> lazy;
    public:
        lazysum(int size): seg(size),lazy(size){}
        void upd(int ind , int l, int r, int st, int ed, ll val){
            if (lazy[ind]!=0){
                seg[ind]=lazy[ind]*(r-l+1ll)%MOD;
                if (r!=l)
                lazy[ind*2]=lazy[ind*2+1]=lazy[ind];
                lazy[ind]=0;
            }
            if (l>ed || r<st)
                return;
            if (l>=st && r<=ed){
                lazy[ind]=val;
                seg[ind]=lazy[ind]*(r-l+1ll)%MOD;
                return;
            }
            int m=(l+r)/2;
            upd(ind*2,l,m,st,ed,val); upd(ind*2+1,m+1,r,st,ed,val);
            seg[ind]=(seg[ind*2]+seg[ind*2+1])%MOD;
        }

        ll get(int ind, int l, int r, int st, int ed){
            if (lazy[ind]!=0){
                seg[ind]=lazy[ind]*(r-l+1ll)%MOD;
                if (r!=l)
                lazy[ind*2]=lazy[ind*2+1]=lazy[ind];
                lazy[ind]=0;
            }
            if (l>ed || r<st)
                return 0ll;

            if (l>=st && r<=ed){
                return seg[ind];
            }

            int m=(r+l)/2;
            return (get(ind*2,l,m,st,ed)+get(ind*2+1,m+1,r,st,ed))%MOD;
        }

};

class segtreemx{

    private:
        vector <ll > seg;

    public:
        segtreemx(int size): seg(4*size,-1){

        }

        void add(int ind , int l, int r, ll i,ll val){
            if (l==r){
                seg[ind]=val;
                return;
            }
            int m=(r+l)/2;
            if (m>=i)
                add(ind*2,l,m,i,val);
            else
                add(ind*2+1,m+1,r,i,val);
            seg[ind]=max(seg[ind*2],seg[ind*2+1]);
        }

        int getmx(int ind, int l, int r,int st, int ed){
            if (l>ed || r<st)
                return -1ll;
            if (l>=st && r<=ed)
                return seg[ind];
            int m=(l+r)/2;
            return max(getmx(ind*2,l,m,st,ed),getmx(ind*2+1,m+1,r,st,ed));
        }

};


vector<int> DistinctSum(vector<int> &arr) {
    int n = arr.size();

    int sum = accumulate(arr.begin(), arr.end(), 0);


    bitset<100001> dp;

    dp[0] = 1;

    for (int i = 0; i < n; ++i) {

        dp |= dp << arr[i];
    }

    vector<int> res;
    for (int i = 0; i <= sum; ++i) {
        if (dp[i]) {

            res.push_back(i);
        }
    }

    return res;
}

int lengthOfLIS(vector<ll>& arr)
{

    ll n = arr.size();
    vector<ll> ans;


    ans.push_back(arr[0]);

    for (ll i = 1; i < n; i++) {
        if (arr[i] > ans.back()) {


            ans.push_back(arr[i]);
        }
        else {

            ll low = lower_bound(ans.begin(), ans.end(),
                                  arr[i])
                      - ans.begin();

            ans[low] = arr[i];
        }
    }


    return ans.size();
}
void solve()
{

    int n;
    cin>>n;
    vector <int> a(n+1);
    for (int i=1;i<=n;i++)
        cin>>a[i];
    vector <bool> b(n+1);
    b[n]=1;
    vector <ll> dp(n+1);
    dp[n]=n;
    for (int i=n-1;i>0;i--){
        b[i]=b[i+1]&(a[i+1]==-1 || a[i+1]==i);
        if (a[i]==-1)
            dp[i]=(dp[i+1]+(n-1)*b[i])%MOD;
        else {
            if (a[i]==i+1){
                dp[i]=dp[i+1];
            }
            else {
                dp[i]=b[i];
            }
        }
    }
    cout<<dp[1];
}// end of solve function





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

    //cout.tie(nullptr);

    //freopen( "palindrome.in" , "r" , stdin );
    //freopen( "palindrome.out" , "w" , stdout );

//    int N=1e5+2;
//    seive(N);
//
    //factorial(2e5+5, MOD7);
//    invfact(N,MOD7);

    //genp(MOD7);

    //precal();


    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

/*



*/

Submission Info

Judge Result