write a go solution for F. Fancy Stacktime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputLittle Fiona has a collection of n blocks of various sizes a_1,a_2,ldots,a_n, where n is even. Some of the blocks can be equal in size. She would like to put all these blocks one onto another to form a fancy stack.Let b_1,b_2,ldots,b_n be the sizes of blocks in the stack from top to bottom. Since Fiona is using all her blocks, b_1,b_2,ldots,b_n must be a permutation of a_1,a_2,ldots,a_n. Fiona thinks the stack is fancy if both of the following conditions are satisfied:   The second block is strictly bigger than the first one, and then each block is alternately strictly smaller or strictly bigger than the previous one. Formally, b_1<b_2>b_3<b_4>ldots>b_n-1<b_n.  The sizes of the blocks on even positions are strictly increasing. Formally, b_2<b_4<b_6<ldots<b_n (remember that n is even).   Two stacks are considered different if their corresponding sequences b_1,b_2,ldots,b_n differ in at least one position.Fiona wants to know how many different fancy stacks she can build with all of her blocks. Since large numbers scare Fiona, find this number modulo 998,244,353.InputEach input contains multiple test cases. The first line contains the number of test cases t (1<=t<=2500). Description of the test cases follows.The first line of each test case contains a single integer n — the number of blocks at Fiona's disposal (2<=n<=5000; n is even). The second line contains n integers a_1,a_2,ldots,a_n — the sizes of the blocks in non-decreasing order (1<=a_1<=a_2<=...b<=a_n<=n).It is guaranteed that the sum of n over all test cases does not exceed 5000.OutputFor each test case, print the number of ways to build a fancy stack, modulo 998,244,353.ExampleInput241 2 3 481 1 2 3 4 4 6 7Output2
4. Output only the code with no comments, explanation, or additional text.