Jury Meeting solution codeforces – nn people gathered to hold a jury meeting of the upcoming competition, the ii-th member of the jury came up with aiai tasks, which they want to share with each other.

Jury Meeting solution codeforces

nn people gathered to hold a jury meeting of the upcoming competition, the ii-th member of the jury came up with aiai tasks, which they want to share with each other.

First, the jury decides on the order which they will follow while describing the tasks. Let that be a permutation pp of numbers from 11 to nn (an array of size nn where each integer from 11 to nn occurs exactly once).

Then the discussion goes as follows:

  • If a jury member p1p1 has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.
  • If a jury member p2p2 has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.
  • If a jury member pnpn has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped.
  • If there are still members with tasks left, then the process repeats from the start. Otherwise, the discussion ends.

A permutation pp is nice if none of the jury members tell two or more of their own tasks in a row.

Count the number of nice permutations. The answer may be really large, so print it modulo 998244353998244353.

Input

The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases.

The first line of the test case contains a single integer nn (2n21052≤n≤2⋅105) — number of jury members.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the number of problems that the ii-th member of the jury came up with.

The sum of nn over all test cases does not exceed 21052⋅105.

Output

For each test case, print one integer — the number of nice permutations, taken modulo 998244353998244353.

Example

input

Copy
4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3

output

Copy
1
6
0
540

C++

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=998244353;
int n,a[N],T,fac[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);fac[0]=1;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),fac[i]=1ll*fac[i-1]*i%mod;
sort(a+1,a+n+1);
if(a[n]==a[n-1]) printf("%d\n",fac[n]);
else if(a[n]>a[n-1]+1) puts("0");
else{
int ct=0;
for(int j=n-1;j>=1&&a[j]==a[n-1];--j) ct++;
int ans=1ll*ct*fac[ct]%mod;
for(int i=ct+2;i<=n;++i) ans=1ll*ans*i%mod;
printf("%d\n",ans);
}
}
return 0;
}

Java

import java.util.*;
import java.io.*;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
public class EdB {
static long[] mods = {1000000007, 998244353, 1000000009};
static long mod = mods[1];
public static MyScanner sc;
public static PrintWriter out;
public static void main(String[] largewang) throws Exception{
// TODO Auto-generated method stub
sc = new MyScanner();
out = new PrintWriter(System.out);
long[] fact = new long[200001];
fact[0] = 1;
for(int j = 1;j<=200000;j++){
fact[j] = ((long)j*fact[j-1])%mod;
}
int t = sc.nextInt();
while (t-->0) {
int n = sc.nextInt();
int[] arr = readArrayInt(n);
sort(arr);
if (arr[n-1] > arr[n-2] + 1)
out.println(0);
else if (arr[n-1] == arr[n-2]) {
out.println(fact[n]);
} else {
int index = n-3;
int count = 1;
while(index >= 0 && arr[index] == arr[n-2]) {
index--;
count++;
}
long ans = fact[n];
ans *= count;
ans %= mod;
ans *= inv(count+1);
ans %= mod;
out.println(ans);
}
}
out.close();

}
public static long inv(long n){
return power(n, mod-2);
}

public static void sort(int[] array){
ArrayList<Integer> copy = new ArrayList<>();
for (int i : array)
copy.add(i);
Collections.sort(copy);
for(int i = 0;i<array.length;i++)
array[i] = copy.get(i);
}
static String[] readArrayString(int n){
String[] array = new String[n];
for(int j =0 ;j<n;j++)
array[j] = sc.next();
return array;
}
static int[] readArrayInt(int n){
int[] array = new int[n];
for(int j = 0;j<n;j++)
array[j] = sc.nextInt();
return array;
}
static int[] readArrayInt1(int n){
int[] array = new int[n+1];
for(int j = 1;j<=n;j++){
array[j] = sc.nextInt();
}
return array;
}
static long[] readArrayLong(int n){
long[] array = new long[n];
for(int j =0 ;j<n;j++)
array[j] = sc.nextLong();
return array;
}
static double[] readArrayDouble(int n){
double[] array = new double[n];
for(int j =0 ;j<n;j++)
array[j] = sc.nextDouble();
return array;
}
static int minIndex(int[] array){
int minValue = Integer.MAX_VALUE;
int minIndex = -1;
for(int j = 0;j<array.length;j++){
if (array[j] < minValue){
minValue = array[j];
minIndex = j;
}
}
return minIndex;
}
static int minIndex(long[] array){
long minValue = Long.MAX_VALUE;
int minIndex = -1;
for(int j = 0;j<array.length;j++){
if (array[j] < minValue){
minValue = array[j];
minIndex = j;
}
}
return minIndex;
}
static int minIndex(double[] array){
double minValue = Double.MAX_VALUE;
int minIndex = -1;
for(int j = 0;j<array.length;j++){
if (array[j] < minValue){
minValue = array[j];
minIndex = j;
}
}
return minIndex;
}
static long power(long x, long y){
if (y == 0)
return 1;
if (y%2 == 1)
return (x*power(x, y-1))%mod;
return power((x*x)%mod, y/2)%mod;
}
static void verdict(boolean a){
out.println(a ? "YES" : "NO");
}
public static class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} 
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try{
str = br.readLine();
} 
catch (IOException e) {
e.printStackTrace();
}
return str;
}

} 
}

 

Python

from functools import lru_cache
M = 998244353

fs = [1, 1]
def factorial(n):
while n >= len(fs):
fs.append(fs[-1] * len(fs) % M)
return fs[n]


for _ in range(int(input())):
n = int(input())
a = sorted(map(int, input().split()))
if a[-1] == a[-2]:
ans = factorial(n)
elif a[-1] == a[-2] + 1:
x = 1
i = n - 2
while i - 1 >= 0 and a[i-1] == a[-2]:
i -= 1
x += 1
ans = factorial(n) * x * pow(x + 1, -1, M)
else:
ans = 0
print(ans % M)

Also read : Jury Meeting solution codeforces

Leave a Reply

Your email address will not be published. Required fields are marked *

*