mob.java

import java.util.*;

public class mob{
	public static void main(String[] args){		

		int[][] in = readPerm(args);
		int[] sigma = in[0];
		int[] pi = in[1];
		
		System.out.print("Interval [");
		printPerm(sigma,pi);
		System.out.println("]");
	
		int m = mob(sigma,pi);
		int occ = NumOccurrences(sigma,pi);
		int ne = NE(sigma,pi);
		int s = secondPart(sigma,pi,m,ne);
		ArrayList<String> lambdas = mobNEprint(sigma,pi);

		System.out.println();
		System.out.println("Mobius function = " + m);
		System.out.println("<br>");
		System.out.println("Number of Occurrences = " + occ);
		System.out.println("Number of Normal Occurrences/Embeddings = " + ne);
		System.out.println();
		System.out.println("Value of second part s = " + s);
		System.out.println();
		if(lambdas.size() > 0) System.out.println("Lambdas in [sigma,pi) with nonzero mu(sigma,lambda)*EZ(lambda,sigma):");
		for(int i = 0; i < lambdas.size(); i++) System.out.println(lambdas.get(i));
		
	}
	
/***************************************************************/
	//main methods for computing MF	
	
	
	private static int mob(int[] sigma, int[] pi){
		if(!Contains(sigma,pi)) return 0;
		if(Arrays.equals(sigma,pi)) return 1;
		Interval I = new Interval(sigma,pi);
		return I.Mobius();
	}
	
	//same as mobNE above but prints what each element of the formula contributes
	private static ArrayList<String> mobNEprint(int[] sigma, int[] pi){
		int[][] o = Occurrences(sigma,pi);
		int[][] occ = occQuotient(o,pi);
		int[] adjs = adjLocBoth(pi);
		int num = 0;


		//get all perms in the interval
		Interval I = new Interval(sigma,pi);

		//get all perms
		ArrayList<int[]> perms  = I.listAllPerms();

		int s,mob,temp;
		ArrayList<String> out = new ArrayList<String>();
		
		//compute EZ(sigma,pi), add to num and print if EZ is none empty
		String t = permString(perms.get(0));
		s = incExSum(perms.get(0),pi,occ);
		permString(perms.get(0));
		if(s!=0){t += " : Contributes = " + s +" : product of mu = 1 and EZ = " + s;out.add(t);}
		
		
		//loop through all elements of (sigma,pi)
		for(int i = 1; i< perms.size(); i++){
			t = "";
			if(pi.length-perms.get(i).length>0){
				//print lambda and compute EZ(lambda,pi)
				s = incExSum(perms.get(i),pi);
				if(!emptyEZ(perms.get(i),pi)){
					t += permString(perms.get(i));
					//if EZ is non empty compute mu(sigma,lambda) and print all
					mob = mob(sigma,perms.get(i));
					temp = s*mob;
					t +=" : Contributes = " + temp + " : product of mu = " + mob + " and EZ = " + s;
					if(temp!=0) out.add(t);
				}
			}
		}
		
		return out;
	}


	//Quotients the occurrences based upon equiv rel of differing only in adjacencies
	private static int[][] occQuotient(int[][] occ,int[] pi){
		//inc records whether to include occ[i] and is intialised to all 1's
		int[] inc = new int[occ.length];
		for(int i = 0; i < inc.length; i++) inc[i] = 1;
		
		//find all the adjacency blocks
		ArrayList<int[]> adjBl = maximalAdjBlocks(pi);
		for(int i = 0; i < occ.length; i++){
			for(int j = 0; j < adjBl.size(); j++){
			//for each adjacency block look though the occurence at that block and see if there is a non zero letter to the left of a zero
			// if ther is set that occurence to be not included.
				for(int k = adjBl.get(j)[0]+1; k <= adjBl.get(j)[1]; k++){
					if(!con(k,occ[i]) && con(k-1,occ[i])) inc[i] = 0;
				}
			}
		}
		
		//create a new array only including the quotiented occurences.
		int count = 0;
		for(int i = 0; i < inc.length; i++){ if(inc[i] == 1) count++;}
		int[][] ret = new int[count][occ[0].length];
		count = 0;
		for(int i = 0; i < inc.length; i++){ if(inc[i] == 1){ret[count]=occ[i];count++;}}
		return ret;
	}
	
	//returns number of normal occurrences
	private static int NE(int[] sigma, int[] pi){
		//get set of occurrences and positions of all tails of adjacencies
		int[][] occ = Occurrences(sigma,pi);
		int[] adjs = adjLocBoth(pi);
		int num = 0;

		//for each occurrence check if the all the tails appear in it, if so add 1 to num
		for(int i = 0; i < occ.length; i++){
			if(subArray(adjs,occ[i])) num++;
		}
		return num;
	}
	
	//returns the second part of the formula
	private static int secondPart(int[] sigma, int[] pi,int mob,int NE){
		//subtract sNE(sigma,pi) from mu(sigma,pi)
		return (mob - (int)Math.pow(-1,pi.length-sigma.length)*NE);
	}
	
	//returns sum over EZ^{lambda,pi}
	private static int incExSum(int[] lambda, int[] pi){
		//get set of occurrences and tehen quotient them
		int[][] o = Occurrences(lambda,pi);
		int[][] occ = occQuotient(o,pi);
		int num = 0;

		//create a binary string which indicates which elements of occ to test if in EZ
		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
		int s;
	
		//intialise array as all 1's
		for(int j = 0; j < bin.length; j++) bin[j] = 1;
		//because EZ is upwards closed check if the set of all elemebts of occ are in EZ and if not then nothing is
		if(!emptyZeroes(bin,occ,pi.length)) return 0;

		//add (-1)^|S| for each S that has empty zero intersection, where S is displayed as a binary string relating to occ
		for(long i = m-1; i > 0; i--){
			bin = BinaryIntArray(i, occ.length);
			s = sum(bin);
			if(s!=1){
				if(emptyZeroes(bin,occ,pi.length)){
					//System.out.println(Arrays.toString(bin));
					num += Math.pow(-1,s);
				}
			}
		}

		return num;
	}

	//returns true if EZ^{lambda,pi} is empty
	private static boolean emptyEZ(int[] lambda, int[] pi){
		int[][] o = Occurrences(lambda,pi);
		int[][] occ = occQuotient(o,pi);

		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
	
		for(int j = 0; j < bin.length; j++) bin[j] = 1;
		if(!emptyZeroes(bin,occ,pi.length)) return true;
		return false;
	
	}
	//returns true if EZ^{lambda,pi} is empty
	private static boolean emptyEZ(int[] lambda, int[] pi,int[][] occ){
		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
	
		for(int j = 0; j < bin.length; j++) bin[j] = 1;
		if(!emptyZeroes(bin,occ,pi.length)) return true;
		return false;
	
	}

	//returns sum over EZ^{lambda,pi}, same incExSum above to be used when occ is already known
	private static int incExSum(int[] lambda, int[] pi, int[][] occ){
		int num = 0;

		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
		int s;
	
		for(int j = 0; j < bin.length; j++) bin[j] = 1;
		if(!emptyZeroes(bin,occ,pi.length)) return 0;
	
		//add (-1)^|S| for each S that has empty zero intersection, where S is displayed as a binary string relating to occ
		for(long i = m-1; i > 0; i--){
			bin = BinaryIntArray(i, occ.length);
			s = sum(bin);
			if(s!=1){
				if(emptyZeroes(bin,occ,pi.length)){
					//System.out.println(Arrays.toString(bin));
					num += Math.pow(-1,s);
				}
			}
		}
		return num;
	}
	
	private static ArrayList<int[]> EZ(int[] sigma,int[] pi){
		//get occurrences and quotient;
		int[][] o = Occurrences(sigma,pi);
		int[][] occ = occQuotient(o,pi);
		
		//init
		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
		ArrayList<int[]> binList = new ArrayList<int[]>();
	
		//add any nonzero sets to binList
		for(long i = m-1; i > 0; i--){
			bin = BinaryIntArray(i, occ.length);
			if(sum(bin)!=1){
				if(emptyZeroes(bin,occ,pi.length)){
					binList.add(bin.clone());
				}
			}
		}
		
		return binList;
	}
	
	private static ArrayList<int[]> nonZeroEZ(int[] sigma,int[] pi){
		//get occurrences and quotient;
		int[][] o = Occurrences(sigma,pi);
		int[][] occ = occQuotient(o,pi);
		
		//init
		long m = (long)Math.pow(2,occ.length);
		int[] bin = new int[occ.length];
		ArrayList<int[]> binList = new ArrayList<int[]>();
	
		//add any nonzero sets to binList
		for(long i = m-1; i > 0; i--){
			bin = BinaryIntArray(i, occ.length);
			if(sum(bin)!=1){
				if(emptyZeroes(bin,occ,pi.length)){
					binList.add(bin.clone());
				}
			}
		}
		
		return binList;
	}
	
	/***********************************************/
	//printing methods
	private static void printPerm(int[] perm){
		if(perm.length < 10){
			for(int i = 0; i < perm.length; i++){
				System.out.print(perm[i]+1);
			}
		}
		else{
			for(int i = 0; i < perm.length; i++){
				System.out.print(perm[i]+1 + " ");
			}
		}
	}
	
	private static void printPermln(int[] perm){
		printPerm(perm);
		System.out.println("");
	}

	private static void printPerm(int[] perm,int[] pi){
		printPerm(perm);
		System.out.print(" : ");
		printPerm(pi);
		System.out.print("");
	}
	private static void printPermln(int[] perm,int[] pi){
		printPerm(perm);
		System.out.print(" : ");
		printPerm(pi);
		System.out.println("");
	}
	
	//converts the permutation to a string
	private static String permString(int[] a){	
		String  ret = "";
		for( int i = 0; i < a.length; i++) ret += (a[i]+1);
		return ret;
    }
	
/*********************************************/
//methods for reading a interval from input
	//read two permutations
	private static int[][] readPerm(String[] args){
		int[] param = new int[args.length];
    	for(int k = 0; k < args.length; k++) param[k] = Integer.parseInt(args[k]);
		int[] sigma = NumToPerm(param[0]); 
		int[] pi = PermOf(TailFrom(param, 1));
		
		int[][] out = new int[][]{sigma,pi};
		return out;
	}
	
	/**************************************************************/
//various methods needed for creating intervals

	//produces the interval [sigma,pi] as a list of Level objects
	private static ArrayList<Level>  makeInterval(int[] sigma, int[] pi){

		//create empty interval
		ArrayList<Level> interval = new ArrayList<Level>();

		//create and add top level containing pi
		Level toplevel = new Level();
		toplevel.add(pi);
		interval.add(toplevel);
		
		//add middle levels
		for(int i = 0; i < pi.length - sigma.length - 1; i++){
			Level nL = makelevel(interval.get(i),sigma);
			interval.add(nL);
		}
		
		//create and add bottom level containing sigma
		Level bottomlevel = new Level();
		bottomlevel.add(sigma);
		for(int i = 0; i < interval.get(interval.size()-1).length(); i++) bottomlevel.getPerm(0).addCover(i);
		interval.add(bottomlevel);
		
		return interval;
	}
	
	//makes a level of the poset
	private static Level makelevel(Level above, int[] sigma){

		Level newLevel = new Level();
		newLevel.clear();

		//loop through the above level remove each letter from each perm check it 
		//contains sigma and is not already present and then add it to the level
		for(int k = 0; k < above.length(); k++){
			for(int i = 0; i < above.get(k).length; i++){
				int[] redperm = removeLetter(above.get(k),i);
				if(Contains(sigma,redperm)){
					//check if redperm is already in level, if not add it, if so record k as covering redperm
					int c = newLevel.contains(redperm);
					if(c == -1) newLevel.add(redperm,k);
					else newLevel.getPerm(c).addCover(k);
				}
			}
		}
		return newLevel;
	}
	
	//remove letter and reduce all letters with higher value
	private static int[] removeLetter(int[] perm, int index){

		int[] newperm = new int[perm.length-1];

		System.arraycopy(perm,0,newperm,0,index);
		System.arraycopy(perm,index+1,newperm,index,perm.length-index-1);
		
		for(int i = 0; i < newperm.length; i++){
			if(newperm[i] > perm[index]) newperm[i]--;
		}

		return newperm;
	}
	
	//removes all letters perm[start]-perm[end] inclusive and reduces
	private static int[] removeLetters(int[] perm, int start, int end){
		int[] newperm = new int[perm.length-(end-start+1)];

		System.arraycopy(perm,0,newperm,0,start);
		System.arraycopy(perm,end+1,newperm,start,newperm.length-start);

		return reduce(newperm);
	}
	//removes all letters at the positions in locs
	private static int[] removeLetters(int[] perm, int[] locs){
		int[] newperm = new int[perm.length-locs.length];

		int t = 0;
		for(int i = 0; i < perm.length; i++){
			if(!con(i,locs)){
				newperm[t] = perm[i];
				t++;
			}
		}

		return reduce(newperm);
	}

	
/*********************************************************************/
//various methods used for computing MF
	//sums the elements pi_start+...+pi_{end-1}
	private static int sum(int start, int end, int[] pi){
		int s = 0;
		for(int i = start; i < end; i++) s += Math.abs(pi[i]);
		return s;
	}
	//sums all elements of bin
	private static int sum(int[] bin){
		int s = 0;
		for(int i = 0; i < bin.length; i++) s+=bin[i];
		return s;
	}	
	//sums abs of all elements of bin
	private static int sumAbs(int[] bin){
		int s = 0;
		for(int i = 0; i < bin.length; i++) s+=Math.abs(bin[i]);
		return s;
	}
	
	//returns true if the array pi contains the number i
	private static boolean con(int i, int[] pi){
		if(pi.length == 0) return false;
		for(int j = 0; j < pi.length; j++){
			if(pi[j] == i) return true;
		}
		return false;
	}
	//returns true if the array pi contains the number i
	private static boolean con(int i, int[][] pi){
		if(pi.length == 0) return false;
		for(int j = 0; j < pi.length; j++){
			if(pi[j] != null){
			for(int k = 0; k < pi[j].length; k++){
				if(pi[j][k] == i) return true;
				if(pi[j][k] == i) return true;
			}}
		}
		return false;
	}
	
	//lists all maximal Adjacency blocks in pi
	private static ArrayList<int[]> maximalAdjBlocks(int[] pi){
		int pos, j;
		int i = 0;
		ArrayList<int[]> out = new ArrayList<int[]>();
		while(i < pi.length){
			//sets pos to increasing or decreasing adj
			if(i < pi.length-1 && pi[i] <  pi[i+1]) pos = 1;
			else pos = -1;
		
			//finds how long adj is
			j = i+1;
			while(j < pi.length && pi[j-1] == pi[j]-pos) j++;
		
			if(i == j-1) pos = 0;
			//adds adj to out
			out.add(new int[]{i,j-1, pos});
		
			i = j;
		}
	
		return out;
	}	
	
	//returns an array of all positions of perm in the tail of an adjacency
	private static int[] adjLocBoth(int[] perm){
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i = 1; i < perm.length; i++){
			if(perm[i-1] == perm[i]-1){
				list.add(i);
			}
			if(perm[i-1] == perm[i]+1){
				list.add(i);
			}
		}

		int[] arr = new int[list.size()];

		for(int i = 0; i < list.size(); i++){
			arr[i] = list.get(i);
		}
	
		return arr;
	}

	//returns the number of adjacencies
	private static int Adj(int[] pi){
		return maximalAdjBlocks(pi).size();
	}
	
	//checks that all of a is in b
	private static boolean subArray(int[] a, int[] b){
		if(b.length < a.length) return false;
		int i = 0;
		boolean found = false;
		while(i < a.length){
			int j = 0;
			found = false;
			while(j < b.length && !found){
				if(a[i] == b[j]) found = true;
				j++;
			}
			if(j == b.length && !found) return false;
			i++;
		}
		return true;
	}
	
	//gives perm in reduced form
	private static int[] reduce(int[] perm){
		if(perm.length == 0) return perm;
	
		int min = 0;
		int max = 0;
	
		int[] redperm = new int[perm.length];
		for(int i = 0; i < perm.length; i++){ if(perm[i] > perm[max]) max = i; 
											if(perm[i] < perm[min]) min = i;} 
		redperm[min] = 0;
		int count = 1;
		int oldmin = min;
		min = max;

		while(count < perm.length){
			for(int i = 0; i < perm.length; i++){
				if(perm[i] < perm[min] && perm[i]>perm[oldmin]) min = i;
			}
			redperm[min] = count;
			oldmin = min;
			min = max;
			count++;
		}
		return redperm;
	}

	
	//if the set S indicated by binary string bin has empty zero set intersection return true
	private static boolean emptyZeroes(int[] bin, int[][] occ, int n){
		for(int i = 0; i < n; i++){
			boolean allZero = true;
			for(int j = 0; j < bin.length; j++){
				if(bin[j] == 1 && con(i,occ[j])) allZero = false;
			}
			if(allZero) return false;
		}
		return true;
	}

	//changes data to next permutation lexicographically and returns false if data is decreasing perm
	private static boolean my_next_permutation(int[] data) {
		int n=data.length;
		int i,j,k,temp;
		i=n-2;
			while (i>=0 && data[i]>=data[i+1]) --i;
			if (i<0) {
				for (j=0,k=n-1; j<k; j++,k--) {
					temp=data[j];
					data[j]=data[k];
					data[k]=temp;
				}
				return false;
			}
			j=n-1;
			while (data[i]>=data[j]) --j;
			temp=data[i];
			data[i]=data[j];
			data[j]=temp;
			for (j=i+1,k=n-1; j<k; j++,k--) {
				temp=data[j];
				data[j]=data[k];
				data[k]=temp;
			}
		return true;
	}
	
/*************************************************************/
//various methods taken from e.java
	private static int[] NumToPerm(int number){

		int Dim;

		for(Dim = 0; number/((int)Math.pow(10,Dim)) > 0; Dim++);
 
		int[] perm = new int[Dim];

		for(int k = Dim-1; k >= 0; k--){
			perm[k] = number%10-1;
			number = number/10;
		}
		return perm; 
	}
	  
	private static int[] TailFrom(int[] A, int start){

		if(A == null)
		return null;

		int[] output = new int[A.length-start];

		for(int k = start; k < A.length; k++)
		output[k-start] = A[k];

		return output;
	}
	
	private static int[] PermOf(int[] param){

		int dim = param.length;;

		if(dim == 1)
		return StandardPerm(NumToPerm(param[0]));
	     
		return StandardPerm(param); 
	}
	
	private static int[] StandardPerm(int[] perm){
		if(perm == null)
			return null;
		return InvTableToPerm(InversionTable(perm));
	}
	
	private static int[] InvTableToPerm(int[] invTable){

		if(invTable == null || invTable.length == 0)
		return null;

		int dim = invTable.length;

		LinkedList<Integer> list = new LinkedList<Integer>();

		for(int k = 0; k < dim; k++)
		list.add(k);

		int[] perm = new int[dim];

		for(int k = 0; k < dim; k++){
		perm[k] = (int)list.get(invTable[k]);
		list.remove(invTable[k]);
		}

		return perm;
	}

	private static boolean Contains(int[] patt, int[] perm){
		return !Avoids(patt, perm);
	}
	
	//returns number of occurrences
	private static int NumOccurrences(int[] patt, int[] perm){

		if(patt.length > perm.length)
			return 0;

		int sum = 0; 

		int[] set = new int[patt.length];
		set[0] = -1;

		while(NextKSubset(set, perm.length)){
			if(Match(patt, SubSeq(set, perm)))
				sum++;
		}

		return sum;
	}
	
	//returns set of occurrences
	private static int[][] Occurrences(int[] patt, int[] perm){

		if(patt.length > perm.length)
			return null;

		int[][] occurrences = new int[(int) LongChoose(perm.length, patt.length)][patt.length];

		int[] set = new int[patt.length];
		set[0] = -1;
     
		int count = -1;
		while(NextKSubset(set, perm.length)){
			if(Match(patt, SubSeq(set, perm))){
			count++;
			for(int k = 0; k < patt.length; k++)
			occurrences[count][k] = set[k];
		}
		}
     
		count++;

		int[][] output = new int[count][patt.length];

		for(int n = 0; n < count; n++)
		output[n] = occurrences[n];

		return output;
	}

	private static boolean Avoids(int[] patt, int[] perm){

		if(patt.length > perm.length) return true;

		int pattLength = patt.length;
		int dim = perm.length;

		boolean[] string = FirstBinaryKString(dim, pattLength);

		int[] invTable = InversionTable(patt);

		if(Arrays.equals(invTable, InversionTable(SubSeq(string, perm)))) return false;

		while(NextBinaryKString(string)){
			if(Arrays.equals(invTable, InversionTable(SubSeq(string, perm)))){
				return false;
			}
		}

		return true;
	}
 
	private static boolean[] FirstBinaryKString(int n, int k){

		if(n <= 0 || k > n || k < 0) return null;

		boolean[] string = new boolean[n];

		for(int i = 0; i < k; i++) string[i] = true;

		return string;
	}
	
	 private static int[] InversionTable(int[] perm){

		if(perm == null || perm.length == 0) return null;

		int[] table = new int[perm.length];

		for(int k = 0; k < perm.length; k++){
			for(int i = k+1; i < perm.length; i++){
				if(perm[k] > perm[i])
				table[k]++;
			}
		}
		
		return table;
	}
	
	private static boolean NextBinaryKString(boolean[] string){
		if(string == null) return false;

		int dim = string.length;
		int k = 0;
		
		while(string[k] == false)  k++; 

		int firstOne = k;

		while(k < dim && string[k] == true){
			string[k] = false;
			k++;
		}

		if(k == dim) return false;

		string[k] = true;
     
		int numOnes = k - firstOne;

		for(int i = 0; i < numOnes-1; i++)
			string[i] = true;

		return true;
	}
	
	 private static int[] SubSeq(boolean[] string, int[] perm){
 
		if(perm == null || string == null || string.length != perm.length) return null;
     
		int numOnes = 0;
		for(int k = 0; k < string.length; k++){
			if(string[k]) numOnes++;
		}

		int[] output = new int[numOnes];

		int count = 0;
		for(int k = 0; k < string.length; k++){
			if(string[k]) output[count++] = perm[k];
		}
		
		return output;
	}
	
	private static int[] SubSeq(int[] subset, int[] perm){
 
		if(perm == null || subset == null || subset.length > perm.length)
			return null;
     
		int[] output = new int[subset.length];

		for(int k = 0; k < subset.length; k++)
			output[k] = perm[subset[k]];

		return output;
	}
	
	 private static boolean NextKSubset(int[] set, int dim){
		if(set.length > dim)
		return false;

		if(set == null || set.length == 0)
			return false;

		int  size = set.length;

		if(set[0] == -1){//return the first set 
			for (int k = 0; k < size; k++)
				set[k] = k;
			return true;
		}
     
		int k = 1;
     
		while(k < size && set[k] == set[k-1]+1)
			k++;

		if(k < size){//found an element exceeding its predecessor by > 1
			set[k-1]++;
         
			for(int i = 0; i < k-1; i++)
				set[i] = i;

			return true;
		}

		//k ==  size.  if last element is maximal, we are done
		if(set[k-1] == dim-1)
			return false;

		//last element is not maximal
		set[k-1]++;
     
		for(int i = 0; i < k-1; i++)
			set[i] = i;
     
		return true;
	}
	 private static int Choose(int n, int k){
     int adhoc, m;
 
     if (k < 0 || k > n) 
         return(0);

     if (k > (n / 2)) k = n - k;
 
     adhoc = 1;
 
     for (m = 0; m < k; m++)
         adhoc = adhoc*(n-m);
 
     return(adhoc / Factorial(k));
 }
  private static int Factorial(int n){
     if (n < 0) 
         return(0);
 
     if (n == 0) 
         return(1);
 
     return n*Factorial(n-1);
 }
	private static long LongChoose(int n, int k){
		long adhoc, m;
 
		if (k < 0 || k > n) 
			return(0);

		if (k > (n / 2)) k = n - k;
 
		adhoc = 1;
 
		for (m = 0; m < k; m++)
			adhoc = adhoc*(n-m);
 
		return(adhoc / LongFactorial(k));
	}
	
	private static long LongFactorial(int x) {
		if (x < 0)
		return 0;
		long fact = 1;
		
		while(x > 1) {
			fact = fact * x;
			x = x - 1;
		}
		
		return fact;
	}
	
	private static int iBit(int n, int i){
		return (n >> i) & 01;
	}
	private static long iBit(long n, int i){
		return (n >> i) & (long)01;
	}
	
	
		/**  Does seq have a subsequence whose letters are in the same
	relative order as those in patt, where we allow repeated letters in
	both?  **/
	private static boolean Match(int[] patt, int[] seq){

		if(patt.length != seq.length)
			return false;

		int dim = seq.length;

		for(int n = 0; n < dim; n++)
		for(int k = n+1; k < dim; k++)
			if(Diff(patt[n], patt[k]) != Diff(seq[n], seq[k])) return false;
		
		return true;
	}
	
	
	private static int Diff(int a, int b){

		if(a < b)
		return -1;

		if(a == b)
		return 0;

		if(a > b)
		return 1;

		return -100;
	}
	
	
	private static int[] BinaryIntArray(int n, int dim){
		int[] output = new int[dim];

		for(int k = 0; k < dim; k++)
			if(iBit(n,k) == 1)
				output[k] = 1;

		return output;
	}
	private static int[] BinaryIntArray(long n, int dim){
		int[] output = new int[dim];

		for(int k = 0; k < dim; k++)
			if(iBit(n,k) == 1)
				output[k] = 1;

		return output;
	}
	





			
		
		
		
		
		
		
		
//Interval Class		
private static class Interval{
	//interval is always of the form [sigma,pi], that is, sigma at bottom, pi at top
	//inter contains all levels of the interval including pi at top and sigma at bottom
	//note the levels are in decreasing lengths so inter.get(0) contains pi
	private ArrayList<Level> inter = new ArrayList<Level>();
	
	//create an empty interval
	public Interval(){
		ArrayList<Level> inter = new ArrayList<Level>();
	}
	
	//create the interval [sigma,pi]
	public Interval(int[] sigma, int[] perm){
		inter = makeInterval(sigma,perm);
	}
	
	//add a level at the bottom of the interval
	public void add(Level l){
		inter.add(l);
	}
	
	//returns size of inter
	public int size(){
		return inter.size();
	}
	
	//returns the i'th largest level
	public Level get(int i){
		return inter.get(i);
	}
	
	//returns the Mobius function of the interval
	//note we actually compute the Mobius function of the dual poset so we return mu*(pi,sigma)
	public int mob(){
		return inter.get(inter.size()-1).getPerm(0).mob();
	}
	
	public int[] sigma(){
		return inter.get(inter.size()-1).get(0);
	}
	public int[] pi(){
		return inter.get(0).get(0);
	}
	
	//print the whole interval
	public void print(){
		for( int i = 0; i < inter.size(); i++){
			inter.get(i).print();
			System.out.println("");
		}
	}
	
	//returns a list of all the perms in the interval starting at sigma finishing at pi
	public ArrayList<int[]> listAllPerms(){
		ArrayList<int[]> list = new ArrayList<int[]>();
		for(int i = inter.size()-1; i >= 0; i--){
			for(int j = 0; j < inter.get(i).length(); j++){
				list.add(inter.get(i).get(j));
			}
		}
		return list;
	}

	//returns a list of all the subintervals
	public ArrayList<int[][]> allSubintervals(){
		ArrayList<int[]> perms = listAllPerms();
		ArrayList<int[][]> sub = new ArrayList<int[][]>();
	
		for(int i = 0; i < perms.size(); i++){
			for(int j = i+1; j <perms.size(); j++){
				if(Contains(perms.get(i),perms.get(j))) sub.add(new int[][]{perms.get(i),perms.get(j)});
			}
		}
		return sub;
	}
	
	//returns number of normal embeddings of sigma in pi
	public int iNE(){
		return NE(sigma(),pi());
	}
	
	//returns the Mobius function
	//actually computes the Mobius function of the dual poset
	public int Mobius(){
		//set mu(pi,pi)=1
		inter.get(0).getPerm(0).setMob(1);
		
		//working from top to bottom compute the mu*(pi,lambda) for all lambda [sigma,pi)
		for(int i = 1; i < inter.size(); i++){
			for(int j = 0; j < inter.get(i).length(); j++){
				computeMob(inter.get(i).getPerm(j), i);
			}
		}
		
		//return mu*(pi,sigma)
		return mob();
	}
	//Computes the mu*(pi,lambda) of the dual poset
	private void computeMob(perm lambda, int interLevel){
		//create an arraylist of everything in (lambda,pi]
		ArrayList<perm> ps = new ArrayList<perm>();
		createUpPoset(lambda,ps,interLevel);
		
		//sum the mobius value of everything in the list
		int mob = 0;
		for(int i = 0; i < ps.size(); i++) mob += ps.get(i).mob();
		
		//negate the sum and store it as the Mobius function of lambda
		lambda.setMob(-mob);	
	}
	
	//adds all elements of the interval [lambda,pi] to the list ps
	private void createUpPoset(perm lambda, ArrayList<perm> ps, int interLevel){
		//loop through all perms that cover lambda
		for(int i = 0; i < lambda.coveredBy().size(); i++){
			//check that ps does not already contain the perm
			if(!ps.contains(inter.get(interLevel-1).getPerm(lambda.coveredBy().get(i)))){
				//if it doesn't add it to ps
				ps.add(inter.get(interLevel-1).getPerm(lambda.coveredBy().get(i)));
				//and recursively add everything that covers perm
				createUpPoset(inter.get(interLevel-1).getPerm(lambda.coveredBy().get(i)),ps,interLevel-1);
			}
		}
	}		
			
}






//the class of levels that the interval is made up off
private static class Level{
	//contains a list of all perms in the level
	private ArrayList<perm> theperms = new ArrayList<perm>();
	
	//create empty level
	public Level(){
		ArrayList<perm> theperms = new ArrayList<perm>();
	}
	
	//create new copy of inputted level
	public Level(Level copy){
		for(int i = 0; i < copy.length(); i++){
			theperms.add(new perm(copy.get(i)));
		}
	}
	
	public int length(){
		return theperms.size();
	}
	
	public void remove(int i){
		theperms.remove(i);
	}
	
	//return the perm at index in array form
	public int[] get(int index){
		return theperms.get(index).theperm;
	}
	//return the perm at index in perm form
	public perm getPerm(int index){
		return theperms.get(index);
	}
	
	//add new perm input an array
	public void add(int[] newperm){
		theperms.add(new perm(newperm));
	}
	//add new perm input an array and the index of a covering perm
	public void add(int[] newperm,int k){
		theperms.add(new perm(newperm,k));
	}
	//add new perm in the form of a perm
	public void add(perm newperm){
		theperms.add(newperm);
	}
	
	//empty the level
	public void clear(){
		theperms.clear();
	}
	
	//check is level contains tocheck, if it does return index else return -1
	public int contains(int[] tocheck){
		for(int i = 0; i < theperms.size(); i++){
			if(Arrays.equals(theperms.get(i).theperm,tocheck)) return i;
		}
		return -1;
	}
	
	//print all perms in the level
	public void print(){
		for(int i = 0; i < theperms.size(); i++){
			printPerm(theperms.get(i).theperm);
			System.out.println();
		}
	}
	
	//print all perms along with their mob value
	public void printMob(){
		for(int i = 0; i < theperms.size(); i++){
			printPerm(theperms.get(i).theperm);
			System.out.println(" " + theperms.get(i).mob());
		}
	}
}
		
		
		
		
private static class perm{
	//theperm is the permutation as an array
	public final int[] theperm;
	//mobValue is used to store the Mobius value of the perm in some interval
	private int mobValue;
	//coveredBy is used for compute mobValue as indicates the indices of the permutations that contain pi on the level above
	private final List<Integer> coveredBy = new ArrayList<Integer>();

	//create the perm
	public perm(int[] in){
		theperm = in;
	}
	//create perm and store index of a perm above that contains it
	public perm(int[] in, int k){
		theperm = in;
		this.coveredBy.add(k);
	}
	
	public int length(){
		return theperm.length;
	}
	
	public void setMob(int i){
		mobValue = i;
	}
	public int mob(){
		return mobValue;
	}
	
	//add to the list of things that cover perm
	public void addCover(int i){
		if(!this.coveredBy.contains(i))this.coveredBy.add(i);
	}
	
	public List<Integer> coveredBy(){
		return coveredBy;
	}
}
		
		
		
		
	
}//end main