# Tara's Beautiful Permutations

### Problem Statement :

```Tara has an array, A, consisting of n integers where each integer occurs at most 2 times in the array.

Let's define P to be a permutation of A where Pi is the ith element of permutation P. Tara thinks a permutation is beautiful if there is no index i such that Pi - P(i+1) = 0 where i ∈ [0, n-1).

You are given q queries where each query consists of some array A. For each A, help Tara count the number of possible beautiful permutations of the n integers in A and print the count, modulo 10^9 +7, on a new line.

Note: Two permutations, P and Q, are considered to be different if and only if there exists an index i such that Pi != Qi and [0, n-1).

Input Format

The first line contains a single integer, q, denoting the number of queries. The 2.q subsequent lines describe each query in the following form:

1.The first line contains an integer, n, denoting the number of elements in array A.
2.The second line contains n space-separated integers describing the respective values of a0, a1, ..., an-1 in array A.
Constraints
1 <= ai <= 10^9
Each integer in A can occur at most 2 times.
For 40% of the maximum score:
1 <= q <= 100
1 <= n <= 1000
The sum of n over all queries does not exceed 10^4.
For 100% of the maximum score:
1 <= q <= 100
1 <= n <= 2000
Output Format

For each query, print the the number of possible beautiful permutations, modulo 10^9 + 7, on a new line.```

### Solution :

```                            ```Solution in C :

In C++ :

#include <bits/stdc++.h>

using namespace std;

const int MOD=1000000007;

int dp[2001][2001][2];

int rec(int one, int two, int ban)
{
if(one==0 && two==0)
return 1;
int& ret=dp[one][two][ban];
if(ret!=-1)
return ret;
ret=0;
if(one>0)
ret=(ret+1LL*rec(one-1, two, 0)*(one-ban))%MOD;
if(two>0)
ret=(ret+1LL*rec(one+1, two-1, 1)*two)%MOD;
return ret;
}

int main()
{
memset(dp, -1, sizeof dp);
int Q;
scanf("%d", &Q);
while(Q--)
{
int N;
scanf("%d", &N);
map<int, int> m;
for(int i=0; i<N; i++)
{
int a;
scanf("%d", &a);
m[a]++;
}
int one=0, two=0;
for(auto& it: m)
{
if(it.second==1)
one++;
else
two++;
}
printf("%d\n", rec(one, two, 0));
}
return 0;
}

In c :

#include<stdio.h>
#include<stdlib.h>
#define m 1000000007u
#define m2 500000004u
typedef long long unsigned llu;
typedef unsigned u;
int S(const void*x,const void*y){return*(int*)x-*(int*)y;}
u C[2222][2222],A[2222],F[2222];
u P(u b,u e)
{
u r=1;
for(;e;e>>=1)
{
if(e&1)r=r*(llu)b%m;
b=b*(llu)b%m;
}
return r;
}
int main()
{
u t,n,i,j,k,d,r;
for(i=-1;++i<2222;)for(C[i][j=0]=1;j++<i;)
if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=m)C[i][j]-=m;
for(F[i=0]=1;++i<2222;)F[i]=i*(llu)F[i-1]%m;
for(scanf("%u",&t);t--;)
{
scanf("%u",&n);
for(i=-1;++i<n;)scanf("%u",A+i);
qsort(A,n,sizeof(u),S);
for(i=d=0;++i<n;)d+=A[i]==A[i-1];
k=P(m2,d);r=0;
for(i=-1;++i<=d;)
{
j=C[d][i]*(llu)F[n-i]%m*(llu)k%m;
if((k<<=1)>=m)k-=m;
if(i&1)
{
if((r-=j)>m)r+=m;
}
else
{
if((r+=j)>=m)r-=m;
}
}
printf("%u\n",r);
}
return 0;
}

In Python3 :

factorial=[1,]
for i in range(1,2001):
factorial.append(factorial[-1]*i)

pascal=[[0 for y in range(1001)] for x in range(1001)]

for i in range(1001):
pascal[i][0]=1
for j in range(1,i+1):
pascal[i][j]=pascal[i-1][j-1]+pascal[i-1][j]

#print(factorial)

for _ in range(int(input())):
m=int(input())
n=len(set(input().split()))
k=m-n

ans=0
f=1
for j in range(0,k+1):

kCj=pascal[k][j]
ans+=f*kCj*factorial[m-j]//(2**(k-j))
f=f*-1
print(ans%1000000007)```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty