B - Chmax
Source: atcoder
Difficulty: 600

Problem Statement
For a permutation
P = (P_1, P_2, \dots, P_N)
of
(1, 2, \dots, N)
, we define
F(P)
by the following procedure:
There is a sequence
B = (1, 2, \dots, N)
.
As long as there is an integer
i
such that
B_i \lt P_{B_i}
, perform the following operation:
Let
j
be the smallest integer
i
that satisfies
B_i \lt P_{B_i}
. Then, replace
B_j
with
P_{B_j}
.
Define
F(P)
as the
B
at the end of this process. (It can be proved that the process terminates after a finite number of steps.)
You are given a sequence
A = (A_1, A_2, \dots, A_N)
of length
N
. How many permutations
P
of
(1,2,\dots,N)
satisfy
F(P) = A
? Find the count modulo
998244353
.
Constraints
1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\dots
A_N
Output
Print the number, modulo
998244353
, of permutations
P
that satisfy
F(P) = A
.
Sample Input 1
4
3 3 3 4
Sample Output 1
1
For example, if
P = (2, 3, 1, 4)
, then
F(P)
is determined to be
(3, 3, 3, 4)
by the following steps:
Initially,
B = (1, 2, 3, 4)
.
The smallest integer
i
such that
B_i \lt P_{B_i}
is
1
. Replace
B_1
with
P_{B_1} = 2
, making
B = (2, 2, 3, 4)
.
The smallest integer
i
such that
B_i \lt P_{B_i}
is
1
. Replace
B_1
with
P_{B_1} = 3
, making
B = (3, 2, 3, 4)
.
The smallest integer
i
such that
B_i \lt P_{B_i}
is
2
. Replace
B_2
with
P_{B_2} = 3
, making
B = (3, 3, 3, 4)
.
There are no more
i
that satisfy
B_i \lt P_{B_i}
, so the process ends. The current
B = (3, 3, 3, 4)
is defined as
F(P)
.
There is only one permutation
P
such that
F(P) = A
, which is
(2, 3, 1, 4)
.
Sample Input 2
4
2 2 4 3
Sample Output 2
0
Sample Input 3
8
6 6 8 4 5 6 8 8
Sample Output 3
18

C++ solution:
#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define UL __uint128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vmi vector<mint>
#define vii vector<pii>
#define rsz resize
#define ep emplace
#define pb pop_back
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define disc(c) (sort(all(c)), (c).rsz(unique(all(c)) - (c).begin()))
#define ers(S, x) ((S).erase((S).find(x)))
#define bit(k) (1 << (k))
#define Bit(k) (1ll << (k))
#define BIT(k) ((LL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define highbit(x) bit(lg2(x))
#define highbitll(x) Bit(LG2(x))
#define popcnt(x) __builtin_popcount(x)
#define popcntll(x) __builtin_popcountll(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define qer(i, r, l) for (int i(r), i##End(l); i > i##End; i = ~-i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#include "debug.h"
#define errm(x, ...) fprintf(stderr, x, ##__VA_ARGS__)
#define errs(x, ...) errm(x "\n", ##__VA_ARGS__)
#else
#define dbg(...) (__VA_ARGS__)
#define dbgArr(...) (__VA_ARGS__)
#define errm(x, ...) (x, ##__VA_ARGS__)
#define errs(x, ...) (x, ##__VA_ARGS__)
#endif

#define __

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }
template<typename T, typename U> T OxO(T _a, U _b) { return _a == _b ? -1 : _a; }
template<typename T> ll sq(T x) { return (ll)x * x; }

bool Mbe;

template <int MOD> struct modint {
    int num;
    const static __uint128_t brt = ((__uint128_t)(1) << (64)) / MOD;
    modint() { num = 0; }
    modint(int x) { num = x % MOD; }
    modint(ll x) { num = x % MOD; }
    modint<MOD> operator=(int x) {
        num = x % MOD;
        return (*this);
    }
    modint<MOD> operator=(ll x) {
        num = x % MOD;
        return (*this);
    }
    modint<MOD> operator+(modint<MOD> c) const {
        ll x = num + c.num;
        return x >= MOD ? x - MOD : x;
    }
    template <typename T> modint<MOD> operator+(T c) const {
        return (*this) + modint<MOD>(c);
    }
    modint<MOD> operator-(modint<MOD> c) const {
        ll x = num - c.num;
        return x < 0 ? x + MOD : x;
    }
    template <typename T> modint<MOD> operator-(T c) const {
        return (*this) - modint<MOD>(c);
    }
    modint<MOD> operator*(modint<MOD> c) const {
        ll x = (ll)num * c.num;
        x = x - MOD * (brt * x >> 64);
        while (x >= MOD) x -= MOD;
        return x;
    }
    template <typename T> modint<MOD> operator*(T c) const {
        return (*this) * modint<MOD>(c);
    }
    
    modint<MOD> qpow(ll b) const {
        modint<MOD> ml = 1, bs = *this;
        while (b) {
            if (b & 1) ml *= bs;
            bs *= bs, b >>= 1;
        } return ml;
    }
    modint<MOD> inv() const { return qpow(MOD - 2); }
    modint<MOD> operator/(modint<MOD> c) { return (*this) * c.inv(); }
    template <typename T> modint<MOD> operator/(T c) const {
        return (*this) / modint<MOD>(c);
    }
    // operator int() { return num; }

    modint<MOD> operator+=(modint<MOD> c) { return (*this) = (*this) + c; }
    modint<MOD> operator-=(modint<MOD> c) { return (*this) = (*this) - c; }
    template <typename T> modint<MOD> operator*=(T c) {
        return (*this) = (*this) * c;
    }
    modint<MOD> operator/=(modint<MOD> c) { return (*this) = (*this) / c; }
    modint<MOD> operator-() { return MOD - num; }
    friend ostream& operator<<(ostream& w, modint<MOD> x) {
        w << x.num;
        return w;
    }
    friend istream& operator>>(istream& w, modint<MOD> x) {
        w >> x.num;
        x.num %= MOD;
        return w;
    }
    bool operator==(modint<MOD> x) { return num == x.num; }
};

template <typename T, int MOD>
modint<MOD> operator*(T a, modint<MOD> b) { return b * a; }
template <typename T, int MOD>
modint<MOD> operator/(T a, modint<MOD> b) { return b.inv() * a; }

struct FastIO {
    char buf[1 << 20], *p1, *p2;
    char puf[1 << 20], *pf;
    
    FastIO() : p1(buf), p2(buf), pf(puf) {}
    ~FastIO() { fwrite(puf, 1, pf - puf, stdout); }
    
    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }
    
    bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }
    
    char rd() {
        char c = gc(); while (blank(c)) c = gc();
        return c;
    }
    
    template<typename T> T rd() {
        T x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        return f ? -x : x;
    }
    
    int rds(char *s) {
        char c = gc(), *S = s;
        while (blank(c)) c = gc();
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }
    
    int rdl(char *s) {
        char c = gc(), *S = s;
        while (c == '\r' || c == '\n') c = gc();
        while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }
    
    void rd(char &c) { c = rd(); }
    
    void rd(char *s) {
        char c = gc();
        while (blank(c)) c = gc();
        if (c == EOF) { *s = 0; return; }
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        *s = 0;
    }
    
    template<int MOD> void rd(modint<MOD> &x) { x = rd<int>(); }
    
    template<typename T> void rd(T &x) {
        x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        if (f) x = -x;
    }
    
    template<typename T, typename... Ts>
    void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }
    
    template<typename T>
    void rda(T* x, int l, int r) { rep(i, l, r) rd(x[i]); }
    
    template<typename T>
    void rda(T* x, int n) { rep(i, 1, n) rd(x[i]); }
    
    void pc(const char &c) {
        if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
        *pf++ = c;
    }
    
    void prt(char c) { pc(c); }
    void prt(char* s) { while (*s) pc(*s++); }
    void prt(const char* s) { while (*s) pc(*s++); }
    void prt(bool b) { pc(b ? '1' : '0'); }
    void prt(string s) { for (auto &&c : s) pc(c); }
    
    template<typename T> void prt(T x) {
        static int st[41], tp = 0;
        if (x == 0) { pc('0'); return; }
        if (x < 0) x = -x, pc('-');
        while (x) st[++tp] = x % 10, x /= 10;
        while (tp) pc(st[tp--] + '0');
    }
    
    template<int MOD> void prt(modint<MOD> x) { prt(x.num); }
    
    template<typename T> void prt(T *x) { while (*x) pc(*x++); }
    
    template<typename T, typename... Ts>
    void prt(T x, Ts... xs) { prt(x), prt(xs...); }
    
    template<typename T> void prb(T x) { prt(x, ' '); }
    
    template<typename T, typename... Ts>
    void prb(T x, Ts... xs) { prt(x, ' '), prb(xs...); }
    
    template<typename T> void prd(T x) { prt(x, '\n'); }
    
    template<typename T, typename... Ts>
    void prd(T x, Ts... xs) { prt(x, ' '), prd(xs...); }
} IO;

#define rd IO.rd
#define rda IO.rda
#define rds IO.rds
#define rdl IO.rdl
#define ri rd<int>()
#define rl rd<ll>()
#define prt IO.prt
#define prs(...) prt(__VA_ARGS__, '\n')
#define prb IO.prb
#define prd IO.prd
#define edl IO.pc('\n')

// #define MC

#define N 200005
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

using mint = modint<mod>;

int n;
int a[N], b[N];
int c[N], d[N];

struct BITree {
    int s[N];
    
    void mdf(int p, int k) {
        for (int i = max(p, 1); i <= n; i += lowbit(i))
            s[i] += k;
    }
    
    int qry(int p) {
        int res = 0;
        for (int i = min(p, n); i; i -= lowbit(i))
            res += s[i];
        return res;
    }
} T;

void mslv() {
    rd(n), rda(a, n);
    rep(i, 1, n) if (a[i] < i) return prs(0);
    per(i, n, 1) d[i] = a[i] != i ? d[c[i] = b[a[i]]] : i, b[a[i]] = i;
    rep(i, 1, n) if (d[i] != a[i]) return prs(0);
    mint ans = 1;
    rep(i, 1, n) {
        if (c[i]) T.mdf(c[i], 1);
        else ans *= i - T.qry(i), T.mdf(i, 1);
    } prs(ans);
}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    errs("\033[1;34mRunning!\033[0;m");
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #ifdef FILERR
    freopen("Test.err", "w", stderr);
    #endif
    #endif
    mprw();
    #ifdef MC
    int _ = ri;
    while (_--) mslv();
    #else
    mslv();
    #endif
    #ifdef JYR
    errm("%.3lfMB ", abs(&Med - &Mbe) / 1048576.);
    errm("%.0lfms\n", clock() * 1000. / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	n := InputInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = InputInt()
		a[i]--
	}

	l, r := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		l[i], r[i] = inf, -1
	}
	for i := 0; i < n; i++ {
		l[a[i]] = Min(l[a[i]], i)
		r[a[i]] = Max(r[a[i]], i)
	}

	starting_point, destination := make([]bool, n), make([]bool, n)
	for i := 0; i < n; i++ {
		if r[i] != -1 {
			if a[r[i]] != r[i] {
				OutInt(0)
				wt.Flush()
				os.Exit(0)
			}
			starting_point[l[i]] = true
			destination[r[i]] = true
		}
	}

	ans, count := 1, 0
	for i := 0; i < n; i++ {
		if starting_point[i] == true {
			count++
		}
		if destination[i] == true {
			ans *= count
			ans %= MOD
			count--
		}
	}

	OutInt(ans)
}

func Min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func Max(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    static In in = new In();
    static Out out = new Out(false, false);
    static final long inf = 0x1fffffffffffffffL;
    static final int iinf = 0x3fffffff;
    static final double eps = 1e-9;
    static long mod = 998244353;

    int[] f(int[] p) {
        int n = p.length;
        int[] b = new int[n];
        Arrays.setAll(b, i -> i);
        while (true) {
            boolean upd = false;
            for (int i = 0; i < n; i++) {
                if (b[i] < p[b[i]]) {
                    b[i] = p[b[i]];
                    upd = true;
                    break;
                }
            }
            if (!upd) {
                return b;
            }
        }
    }

    void solve() {
        int n = in.nextInt();
        int[] a = in.nextIntArray(n, i -> i - 1);
        List<Integer> ok = new ArrayList<>();
        int[] last = new int[n];
        Arrays.fill(last, -1);
        boolean all = true;
        for (int i = 0; i < n; i++) {
            all &= a[i] >= i;
            all &= a[a[i]] == a[i];
            if (last[a[i]] == -1) {
                last[a[i]] = i;
                ok.add(i);
            }
        }
        if (!all) {
            out.println(0);
            return;
        }
        int j = 0;
        int k = 0;
        long ans = 1;
        for (int i = 0; i < n; i++) {
            if (a[i] != i) continue;
            while (j + 1 < ok.size() && ok.get(j + 1) <= i) {
                j++;
            }
            ans = ans * (j - k + 1) % mod;
            k++;
        }
        out.println(ans);
//        int cor = 0;
//        for (int[] b : new Library.Permutation(a.length)) {
//            if (Arrays.equals(f(b), a)) {
//                cor++;
//            }
//        }
//        out.println(cor);
//        if (ans != cor) throw new RuntimeException();
    }

    public static void main(String... args) {
        new Main().solve();
        out.flush();
    }
}

class In {
    private final BufferedInputStream reader = new BufferedInputStream(System.in);
    private final byte[] buffer = new byte[0x10000];
    private int i = 0;
    private int length = 0;

    public int read() {
        if (i == length) {
            i = 0;
            try {
                length = reader.read(buffer);
            } catch (IOException ignored) {
            }
            if (length == -1) {
                return 0;
            }
        }
        if (length <= i) {
            throw new RuntimeException();
        }
        return buffer[i++];
    }

    public String next() {
        StringBuilder builder = new StringBuilder();
        int b = read();
        while (b < '!' || '~' < b) {
            b = read();
        }
        while ('!' <= b && b <= '~') {
            builder.appendCodePoint(b);
            b = read();
        }
        return builder.toString();
    }

    public String nextLine() {
        StringBuilder builder = new StringBuilder();
        int b = read();
        while (b != 0 && b != '\r' && b != '\n') {
            builder.appendCodePoint(b);
            b = read();
        }
        if (b == '\r') {
            read();
        }
        return builder.toString();
    }

    public int nextInt() {
        long val = nextLong();
        if (val < Integer.MIN_VALUE || Integer.MAX_VALUE < val) {
            throw new NumberFormatException();
        }
        return (int)val;
    }

    public long nextLong() {
        int b = read();
        while (b < '!' || '~' < b) {
            b = read();
        }
        boolean neg = false;
        if (b == '-') {
            neg = true;
            b = read();
        }
        long n = 0;
        int c = 0;
        while ('0' <= b && b <= '9') {
            n = n * 10 + b - '0';
            b = read();
            c++;
        }
        if (c == 0 || c >= 2 && n == 0) {
            throw new NumberFormatException();
        }
        return neg ? -n : n;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public char[] nextCharArray() {
        return next().toCharArray();
    }

    public String[] nextStringArray(int n) {
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = next();
        }
        return s;
    }

    public char[][] nextCharMatrix(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    public int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    public int[][] nextIntMatrix(int h, int w) {
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextIntArray(w);
        }
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    public long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }

    public long[][] nextLongMatrix(int h, int w) {
        long[][] a = new long[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextLongArray(w);
        }
        return a;
    }

    public List<List<Integer>> nextGraph(int n, int m, boolean directed) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            res.get(u).add(v);
            if (!directed) {
                res.get(v).add(u);
            }
        }
        return res;
    }
}

class Out {
    private final PrintWriter out = new PrintWriter(System.out);
    private final PrintWriter err = new PrintWriter(System.err);
    public boolean autoFlush;
    public boolean enableDebug;

    public Out(boolean autoFlush, boolean enableDebug) {
        this.autoFlush = autoFlush;
        this.enableDebug = enableDebug;
    }

    public void debug(Object... args) {
        if (!enableDebug) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        err.println(Arrays.stream(args).map(obj -> format(obj, true)).collect(Collectors.joining(" ")));
        err.flush();
    }

    private String format(Object obj, boolean canMultiline) {
        if (obj == null) return "null";
        Class<?> clazz = obj.getClass();
        if (clazz == Double.class) return String.format("%.10f", obj);
        if (clazz == int[].class) return Arrays.toString((int[])obj);
        if (clazz == long[].class) return Arrays.toString((long[])obj);
        if (clazz == char[].class) return String.valueOf((char[])obj);
        if (clazz == boolean[].class) return IntStream.range(0, ((boolean[])obj).length).mapToObj(i -> ((boolean[])obj)[i] ? "1" : "0").collect(Collectors.joining());
        if (clazz == double[].class) return Arrays.toString(Arrays.stream((double[])obj).mapToObj(a -> format(a, false)).toArray());
        if (canMultiline && clazz.isArray() && clazz.componentType().isArray()) return Arrays.stream((Object[])obj).map(a -> format(a, false)).collect(Collectors.joining("\n"));
        if (clazz == Object[].class) return Arrays.toString(Arrays.stream((Object[])obj).map(a -> format(a, false)).toArray());
        if (clazz.isArray()) return Arrays.toString((Object[])obj);
        return String.valueOf(obj);
    }

    public void println(Object... args) {
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        out.println(Arrays.stream(args)
                .map(obj -> obj instanceof Double ? String.format("%.10f", obj) : String.valueOf(obj))
                .collect(Collectors.joining(" ")));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(char a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(int a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(long a) {
        out.println(a);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(double a) {
        out.println(String.format("%.10f", a));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(String s) {
        out.println(s);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(char[] s) {
        out.println(String.valueOf(s));
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(int[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i : a) {
            joiner.add(Integer.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    public void println(long[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (long i : a) {
            joiner.add(Long.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    public void flush() {
        err.flush();
        out.flush();
    }
}

JavaScript solution:
function Main(input) {
    const [[N], A] = input.map(e => e.split(" ").map(Number));
    const mod = 998244353;
    let ok = true;
    const set = new Set();
    for (let i = N; i > 0; i--) {
        if (!(set.has(A[i - 1])) && A[i - 1] !== i) ok = false;
        set.add(A[i - 1]);
    }
    if (ok) {
        let last = [...new Array(N)].map((_, i) => i + 1);
        const number = new Set(last);
        let line = [];
        for (let i = N; i > 0; i--) {
            if (A[i - 1] === i) {
                line.push(i);
                continue;
            }
            number.delete(last[A[i - 1] - 1]);
            last[A[i - 1] - 1] = i;
        }
        line = line.sort((a, b) => a - b);
        const nums = [...number];
        let ans = 1;
        function lower_bound(num, array) {
            let ok = -1, ng = array.length;
            while (ng - ok > 1) {
                const mid = (ok + ng) >> 1;
                array[mid] <= num ? ok = mid : ng = mid;
            }
            return ok + 1;
        }
        let s = 0;
        for (const n of line) {
            // console.log(n, nums, lower_bound(n, nums));
            const tmp = lower_bound(n, nums);
            // console.log(tmp);
            ans *= (tmp - s);
            ans %= mod;
            s++;
        }
        console.log(ans);
    } else {
        console.log(0);
    }
}
const rl = require('readline').createInterface({ input: process.stdin });
const line = [];
rl.on('line', (input) => line.push(input));
rl.on('close', () => Main(line));

Python solution:
MOD = 998244353

N = int(input())
A = list(map(int, input().split()))

ans, cnt = 1, 0
exist = [False]*(N+1)

for i, a in enumerate(A, 1):
  if a < i or exist[i] and a != i:
    ans = 0
    break
  if not exist[a]:
    cnt += 1
    exist[a] = True
  if exist[i]:
    ans *= cnt; ans %= MOD
    cnt -= 1

print(ans)

Ruby solution:
n = gets.to_i
a = gets.split.map(&:to_i).map{|v|v-1}
b = (0..n-1).to_a
hash = Hash.new(0)
used = Array.new(n,false)
ok = Array.new(n,false)
n.times do |i|
  if a[i] < i
    puts 0
    exit
  elsif a[i] == i
    if hash[i] > 0
      used[i] = true
    end
  else
    if hash[a[i]] > 0
      used[i] = true
    else
      hash[a[i]] += 1
    end
    ok[i] = true
    if a[a[i]] != a[i]
      puts 0
      exit
    end
  end
end
MOD = 998244353
ans = 1
cnt = 0
n.times do |i|
  cnt += 1 if used[i].!
  if ok[i].!
    if cnt <= 0
      puts 0
      exit
    end
    ans *= cnt
    ans %= MOD
    cnt -= 1
  end
end
puts ans