# Extremum Permutations

### Problem Statement :

```Let's consider a permutation P = {p1, p2, ..., pN} of the set of N = {1, 2, 3, ..., N} elements .

P is called a magic set if it satisfies both of the following constraints:

Given a set of K integers, the elements in positions a1, a2, ..., aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1
Given a set of L integers, elements in positions b1, b2, ..., bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1
How many such magic sets are there?

Input Format
The first line of input contains three integers N, K, L separated by a single space.
The second line contains K integers, a1, a2, ... aK each separated by single space.
the third line contains L integers, b1, b2, ... bL each separated by single space.

Output Format
Output the answer modulo 1000000007 (109+7).

Constraints
3 <= N <= 5000
1 <= K, L <= 5000
2 <= ai, bj <= N-1, where i ∈ [1, K] AND j ∈ [1, L]```

### Solution :

```                            ```Solution in C :

In C++ :

#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stdio.h>
#include<map>
#include<ext/hash_map>
#include<ext/hash_set>
#include<set>
#include<string>
#include<assert.h>
#include<vector>
#include<time.h>
#include<queue>
#include<deque>
#include<sstream>
#include<stack>
#include<sstream>
#define MA(a,b) ((a)>(b)?(a):(b))
#define MI(a,b) ((a)<(b)?(a):(b))
#define AB(a) (-(a)<(a)?(a):-(a))
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ep 0.0000000001
#define pi 3.1415926535897932384626433832795

using namespace std;
using namespace __gnu_cxx;
const long long P=1000000000+7;
const int N=5001;

int n,m,i,j,kk,k,l,r;
int a[N];
long long d[N],dd[N];
int main()
{
cin>>n>>k>>l;
for (i=1;i<=k;i++)
{
cin>>j;
a[j]|=1;
a[j+1]|=2;
}
for (i=1;i<=l;i++)
{
cin>>j;
a[j]|=2;
a[j+1]|=1;
}
for (i=2;i<=n;i++)
if (a[i]==3) {cout<<0<<endl; return 0;}
d=1;
for (i=2;i<=n;i++)
{
for (j=1;j<=n;j++)
d[j]=(d[j]+d[j-1])%P;
if (a[i]==2)
{
for (j=1;j<=i;j++)
dd[j]=d[j-1];
} else
if (a[i]==1)
{
for (j=1;j<=i;j++)
dd[j]=(d[n]-d[j-1]+P)%P;
}else
for (j=1;j<=i;j++)
dd[j]=d[n];

for (j=1;j<=n;j++) d[j]=0;
for (j=1;j<=i;j++)
d[j]=dd[j];
// for (j=1;j<=i;j++)
//  cout<<d[j]<<" ";cout<<endl;
}
long long ans=0;
for (i=1;i<=n;i++) ans=(ans+d[i])%P;
cout<<ans<<endl;
return 0;
}

In Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int l = in.nextInt();
int[] a = new int;
int[] b = new int;
long[][] dp = new long;

for (int i = 0; i < k; i++) {
a[in.nextInt()] = 1;
}

for (int i = 0; i < l; i++) {
b[in.nextInt()] = 1;
}

for (int i = 1; i < n; i++) {
if (a[i] == 1 && b[i] == 1){
System.out.println("0");
return;
}
if ((a[i-1] == 1 && a[i] == 1) || (b[i-1]==1 && b[i] == 1)){
System.out.println("0");
return;
}
}

dp = 1;
for (int i = 2; i <= n; i++){
if (!(a[i-1] == 1  || b[i] == 1)){
long sum = 0;
for (int j=1; j <= i; j++){
}
}
if (!(b[i-1] == 1 || a[i] == 1)){
long sum = 0;
for (int j=i; j>=1; j--){
}
}
}

long ans = 0;
for (int i = 1; i <= n; i++){
}

System.out.println(ans);

}

private static long add(long x, long v){
return (x+v) % 1000000007;
}

}

In C :

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int o={0};
long long dp={0};

int main(){
int N,K,L,x,i,j;
long long sum;
scanf("%d%d%d",&N,&K,&L);
for(i=0;i<K;i++){
scanf("%d",&x);
if(o[x-1]==1){
printf("0");
exit(0);
}
o[x-1]=-1;
if(o[x]==-1){
printf("0");
exit(0);
}
o[x]=1;
}
for(i=0;i<L;i++){
scanf("%d",&x);
if(o[x-1]==-1){
printf("0");
exit(0);
}
o[x-1]=1;
if(o[x]==1){
printf("0");
exit(0);
}
o[x]=-1;
}
dp=1;
for(i=1;i<N;i++){
sum=0;
switch(o[i]){
case 0:
for(j=0,sum=0;j<i;j++)
sum=(sum+dp[i-1][j])%MOD;
for(j=0;j<=i;j++)
dp[i][j]=sum;
break;
case -1:
for(j=i-1,sum=0;j>=0;j--){
sum=(sum+dp[i-1][j])%MOD;
dp[i][j]=sum;
}
break;
default:
for(j=0,sum=0;j<i;j++){
sum=(sum+dp[i-1][j])%MOD;
dp[i][j+1]=sum;
}
}
}
for(i=0,sum=0;i<N;i++)
sum=(sum+dp[N-1][i])%MOD;
printf("%lld",sum);
return 0;
}

In Python3 :

from itertools import islice, accumulate

MOD = 10**9 + 7

def permcount(permlen, a, b):
if any(x+1 == y for c in map(sorted, (a, b)) for x, y in zip(c, c[1:])):
return 0
if set(a) & set(b):
return 0
goingup = [None] * permlen
for c, low in ((a, True), (b, False)):
for elt in c:
elt -= 1
if elt > 0:
goingup[elt] = not low
if elt < permlen - 1:
goingup[elt+1] = low
count = 
for i, inc in islice(enumerate(goingup), 1, permlen):
if inc is None:
count = [sum(count)] * (i+1)
elif inc:
count =  + list(accumulate(count))
else:
count = list(reversed(list(accumulate(reversed(count))))) + 
count = [elt % MOD for elt in count]
return sum(count) % MOD

return [int(f) for f in input().split()]

assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))```
```

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio