{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence of $N$ integers: $A_1,A_2,...,A_N$.\nFind the number of permutations $p_1,p_2,...,p_N$ of $1,2,...,N$ that can be changed to $A_1,A_2,...,A_N$ by performing the following operation some number of times (possibly zero), modulo $998244353$:\n\n*   For each $1\\leq i\\leq N$, let $q_i=min(p_{i-1},p_{i})$, where $p_0=p_N$. Replace the sequence $p$ with the sequence $q$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3 × 10^5$\n*   $1 \\leq A_i \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$\n$:$\n$A_N$"},{"iden":"sample input 1","content":"3\n1\n2\n1"},{"iden":"sample output 1","content":"2\n\n$(2,3,1)$ and $(3,2,1)$ satisfy the condition."},{"iden":"sample input 2","content":"5\n3\n1\n4\n1\n5"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"8\n4\n4\n4\n1\n1\n1\n2\n2"},{"iden":"sample output 3","content":"24"},{"iden":"sample input 4","content":"6\n1\n1\n6\n2\n2\n2"},{"iden":"sample output 4","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}