import java.util.*;
import java.io.*;

public class AllocatedMemory {

	public int [ ] memory;		// the memory pool
	private int poolSize;		// size of the memory pool
	private int firstFreeBlock;	// index of header info for first free block
	private boolean DEBUGGING = true;
	private int HEADERSIZE = 3;
	private int TRAILERSIZE = 1;
	
	public static void main (String [ ] args) {
		BufferedReader keyboard 
			= new BufferedReader (new InputStreamReader (System.in));
		AllocatedMemory storage = new AllocatedMemory (20);

		while (true) {
			// Read commands of the form "a #" (in order to allocate 
			// the given number of units), or "f ptr" (in order to free 
			// the space pointed to by the given "pointer". 
			// A "pointer" here is either 0 (representing null) 
			// or a pool array index.
			System.out.println ( );
			System.out.print ("Command? ");
			String line;
			try {
				line = keyboard.readLine ( );
			} catch (Exception e) {
				e.printStackTrace ( );
				break;
			}
			StringTokenizer tokens = new StringTokenizer (line);
			if (tokens.countTokens ( ) == 0) {
				System.out.println (line + " is empty.");
				System.out.println ("Commands are either 'q', 'a #', or 'f ptr'.");
				continue;
			} 
			String cmd = tokens.nextToken ( );
			if (cmd.equals ("q")) {
				return;
			}
			if (!tokens.hasMoreElements ( )) {
				System.out.println (line + " has no argument.");
				System.out.println ("Commands are either 'q', 'a #', or 'f ptr'.");
				continue;
			} 
			int arg;
			try {
				arg = Integer.parseInt (tokens.nextToken ( ));
			} catch (Exception e) {
				System.out.println (line + " has an illegal command.");
				System.out.println ("Commands are either 'q', 'a #', or 'f ptr'.");
				continue;
			}
			if (cmd.equals ("a")) {
				int ptr = storage.allocate (arg);
				if (ptr == 0) {
					System.out.println ("CanŐt allocate!");
				} else {
					// Write a bunch of identifying stuff to the memory just acquired.
					for (int k=ptr; k<ptr+arg; k++) {
						storage.memory[k] = -ptr;
					}
					System.out.println ("'address' of allocated block = " + ptr);
				}
			} else {
				storage.free (arg);
			}
		}
	}

	// Initialize the pool of allocatable memory as a single free block.
	public AllocatedMemory (int size) {
		// memory is treated as an array indexed starting at 1.
		memory = new int [size+1];
		poolSize = size;
		firstFreeBlock = 1;
		// Usable memory in a block is all but one unit at each end.
		setSize (1, poolSize-2);
		setPrev (1, 0);		// no previous block
		setNext (1, 0);		// no next block
		setTrailer (1, poolSize-2);
		debugPrint ( );
	}
	
	//  We have a request for n units.
	//  Return a pointer to n free units of storage from the pool,
	//  choosing it using the first-fit strategy.
	public int allocate (int n) {
	    int b;
	    
		// Make sure this is a reasonable request.
		if (n<=0) {
			return 0;
		}
		
		// Search for a free block at least as large as desired.
		for (b=firstFreeBlock; b!=0 && size(b)<n; b=next(b)) {
		}
		if (b==0) {	// couldn't find one
			return 0;
		}
		
		// We have a free block.
		// First find out exactly how much of the free block is to be used.
		// If the requested size doesn't leave any space in the free block
		// for another free block's header and trailer and some storage,
		// return the whole block.
		int oldBlockSize = size(b);
		int allocBlockSize = n<size(b)-HEADERSIZE-TRAILERSIZE? n: oldBlockSize;
		if (oldBlockSize == allocBlockSize) {
			// The entire free block is used.
			// Merely detach it from the free list and return.
			unlink (b);

			// Update the free block's size too (to show that it's allocated).
			setSize (b, -allocBlockSize);
			setTrailer (b, -allocBlockSize);
		} else {
			// A new, smaller free block is to be created.
			// Insert it into the free list.

			setSize (b, -allocBlockSize);
			setTrailer (b, -allocBlockSize);
			int newBlockLoc = rightBlockLoc (b);
			setSize (newBlockLoc, _____________________________ );
			setTrailer (newBlockLoc, _____________________________ );
		
			// Link new block into the free list. 
			setPrev (newBlockLoc, prev(b));
			if (prev(b) != 0) {
				setNext (prev(b), newBlockLoc);
			} else {
				firstFreeBlock = newBlockLoc;
			}
			setNext (newBlockLoc, next(b));
			if (next(b) != 0) {
				setPrev (next(b), newBlockLoc);
			}
		}
		debugPrint ();
		return b+1;
	}

	//  We have a request to free a block.
	//  The argument points to the array cell immediately after
	//  the cell that starts the header.
	public void free (int ptr) {
		int b = ptr - 1;
		int blockSize;
		boolean blockIsEnlarged = false;
		setSize (b, abs(size(b)));	// Indicate that the block is now free.
		// See if previous adjacent block is free, and combine if so.
		if (leftBlockIsFree (b)) {
			blockSize = ___________________________________ ;
			b = leftBlockLoc(b);
			setSize (b, blockSize);
			// See if next adjacent block is free, and combine if so.
			if (rightBlockIsFree (b)) {
				int adjBlock = rightBlockLoc(b);
				blockSize = ___________________________________ ;
				setSize (b, blockSize);
				unlink (adjBlock);	// Unlink the old block. 
			}
			blockIsEnlarged = true;
		} else if (rightBlockIsFree (b)) {
			// See if next adjacent block is free, and combine if so. 
			int adjBlock = rightBlockLoc(b);
			blockSize = ___________________________________ ;
			setSize (b, blockSize);
			setPrev (b, prev(adjBlock));
			if (prev(b) != 0) {
				setNext (prev(b), b);
			} else {
				firstFreeBlock = b;
			}
			setNext (b, next(adjBlock));
			if (next(b) != 0) {
				setPrev (next(b), b);
			}
			blockIsEnlarged = true;
		}
		setTrailer (b, size(b));
		// If the new free block isn't already in the free list, 
		// add it to the start. 
		if (blockIsEnlarged) {
			debugPrint ( );
			return;
		}
		if (firstFreeBlock != 0) {
			setPrev (firstFreeBlock, b);
		}
		setNext (b, firstFreeBlock);
		setPrev (b, 0);
		firstFreeBlock = b;
		debugPrint ( );
	}

	// Return the index of the trailer for the given block. 
	private int trailerLoc (int b) {
		return b+abs(size(b))+1;
	}

	// Return the size of the given block. 
	private int size (int b) {
		return memory[b];
	}

	// Set the size of the given block to the given value. 
	private void setSize (int b, int newSize) {
		memory[b] = newSize;
	}

	// Return the index of the free block preceding this one. 
	private int prev (int b) {
		return memory[b+1];
	}

	// Set the given block's prev to the given index. 
	private void setPrev (int b, int newPrev) {
		memory[b+1] = newPrev;
	}

	// Return the index of the free block following this one. 
	private int next (int b) {
		return memory[b+2];
	}

	// Set the given block's next to the given index. 
	private void setNext (int b, int newNext) {
		memory[b+2] = newNext;
	}
	// Return the trailer information (i.e. the size) of the given block. 
	private int trailer (int b) {
		return memory[trailerLoc(b)];
	}

	// Set the trailer information of the given block to the given value. 
	private void setTrailer (int b, int value) {
		memory[trailerLoc(b)] = value;
	}

	// Return the index of the block adjacent on the left. 
	private int leftBlockLoc (int b) {
		if (b <= 1) {
			return 0;
		} else {
			return b - memory[b-1] - 2;
		}
	}

	// Return true if the block adjacent on the left is free. 
	private boolean leftBlockIsFree (int b) {
		if (b <= 1) {
			return false;
		} else {
			return memory[b-1] > 0;
		}
	}
	// Return the index of the block adjacent on the right. 
	private int rightBlockLoc (int b) {
		if (trailerLoc(b) >= poolSize) {
			return 0;
		} else {
			return trailerLoc(b)+1;
		}
	}
	// Return true if the block adjacent on the right is free. 
	private boolean rightBlockIsFree (int b) {
		if (trailerLoc(b) >= poolSize) {
			return false;
		} else {
			return memory[trailerLoc(b)+1] > 0;
		}
	}

	// Unlink the block starting at the given index from the free list. 
	private void unlink (int b) {
		if (prev(b) != 0) {
			setNext (prev(b), next(b));
		} else {
			firstFreeBlock = next(b);
		}
		if (next(b) != 0) {
			setPrev (next(b), prev(b));
		}
	}

	// Print memory. 
	private void debugPrint ( ) {
		int k;
		if (DEBUGGING) {
			for (k=1; k<=poolSize; k++) {
				System.out.print (" " + memory[k]);
			}
			System.out.println ( );
			printFreeBlockInfo ();
		}
	}

	// Print information about the free blocks. 
	private void printFreeBlockInfo () {
		int b;
		System.out.println ("Free blocks:");
		for (b=firstFreeBlock; b!=0; b=next(b)) {
			System.out.println ("\tHeader at " + b + "; size = " + size(b) 
				+ "; prev at " + prev(b) + "; next at " + next(b));
			if (size(b) <= 0) {
				System.out.println ("*** Block size is invalid!");
			}
			if (size(b) != trailer(b)) {
				System.out.println ("*** Block sizes are inconsistent!");
			}
			if (prev(b)<0 || prev(b)>poolSize) {
				System.out.println ("*** Invalid prev!");
			}
			if (next(b)<0 || next(b)>poolSize) {
				System.out.println ("*** Invalid next!");
			}
		}
	}
	
	// Return the absolute value of the argument.
	private int abs (int k) {
		return k > 0? k: -k;
	}
}