---{"category_name":"easy","problem_code":"LENGAME","problem_name":"Game of Length","problemComponents":{"constraints":"- $1 \\leq T \\leq 2 \\cdot 10^4$\n- $1 \\leq N \\leq 5 \\cdot 10^5$\n- $1 \\leq A_i \\leq 5 \\cdot 10^5$\n- Sum of $N$ does not exceeds $5 \\cdot 10^5$ over all testcases.\n","constraintsState":true,"subtasks":"","subtasksState":false,"inputFormat":"- First line will contain $T$, number of testcases. Then the testcases follow.\n- Each testcase contains two lines of input.\n- The first line contains $N$ the length of the array.\n- The second line contains $N$ space-separated integers $A_1, A_2,..., A_N$ representing the initial array.\n","inputFormatState":true,"outputFormat":"For each testcase, output in a single line the expected length of Bob\u0027s array at the end of the game modulo $998244353$.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"4\n2\n1 2\n3\n1 2 3\n3\n1 1 1\n3\n2 3 2","output":"499122178\n831870296\n1\n665496237","explanation":"**Test case $1$:** The possible final arrays will be $[2, 1]$ or $[1, 2]$. If Bob chooses indexes in the order $[2, 1]$ then he will end up with $2$ elements in the first case and $1$ element in the second case, if he chooses indexes in the order $[1, 2]$ then he will end up with $1$ element in the first case and $2$ elements in the case. Hence his probability ending up with $2$ elements is $\\frac{1}{2}$ and with $1$ element is also $\\frac{1}{2}$. Hence the final answer will be calculated as $2 \\cdot \\frac{1}{2} + 1 \\cdot \\frac{1}{2}$ which is equal to $\\frac{3}{2}$.\n\n**Test case $2$:** The probability of Bob ending up with all three elements is $\\frac{1}{6}$, the probability that he ends up with any two elements is $\\frac{1}{2}$ and the probability that he ends with only a single element is $\\frac{1}{3}$. Hence the final answer is calculated as $3 \\cdot \\frac{1}{6} + 2 \\cdot \\frac{1}{2} + 1 \\cdot \\frac{1}{3}$ which is equal to $\\frac{11}{6}$.\n\n**Test case $3$:** No matter what index Bob chooses initially he will only end up with $1$ element in his final array. Hence the final expected value is equal to $1$.\n\n**Test case $4$:** The probability of Bob ending up with all three elements is $0$, the probability that he ends up with any two elements is $\\frac{2}{3}$ and the probability that he ends with only a single element is $\\frac{1}{3}$. Hence the final answer is calculated as $2 \\cdot \\frac{2}{3} + 1 \\cdot \\frac{1}{3}$ which is equal to $\\frac{5}{3}$.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"tejas10p","problem_tester":"","date_added":"10-10-2021","tags":{"0":"dynamic","1":"expected","2":"medium","3":"start15","4":"tejas10p"},"problem_difficulty_level":"Unavailable","best_tag":"Dynamic Programming","editorial_url":"https://discuss.codechef.com/problems/LENGAME","time":{"view_start_date":1634060704,"submit_start_date":1634060704,"visible_start_date":1634060704,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=LENGAME","is_proctored":false,"visitedContests":{},"layout":"problem"}---Alice and Bob are given an array of length of $N$. They decide to play a game with it.Initially, Alice randomly shuffles the array, and then Bob takes $N$ turns. In each turn, Bob chooses an index which he has not already chosen and then Alice reveals the number on that index to Bob. If this number is either the first number to be chosen or **strictly larger** than previously chosen numbers by Bob then he takes it and adds to his array else he throws it.You only know the initial unshuffled array and want to know the expected length of Bob's array at the end of the game.The final expected length can be represented as a fraction of the form $\frac{P}{Q}$. You are required to print $P \cdot Q^{-1} \bmod 998244353$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>