// Arup Guha
// 1/20/2024
// Practice Code to show how to use TreeSet and TreeMap

import java.util.*;

public class testds {

	public static void main(String[] args) {
		
		// If we want to time something, use two calls to currentTimeMillis(); and subtract.
		long sT = System.currentTimeMillis();
		testTreeMap();
		long eT = System.currentTimeMillis();
		System.out.println("Time took = "+(eT-sT)+" ms.");
	}
	
	// TreeSet Example
	public static void testTreeSet() {
	
		Random r = new Random();
		
		// Add some random numbers to a tree set. (Do 1000000 to 1000000 to see speed.)
		TreeSet<Integer> ts = new TreeSet<Integer>();
		
		// This is # of values added.
		for (int i=0; i<50; i++) {
			
			// This is range of values.
			int card = r.nextInt(100)+1;
			ts.add(card);
		}
		
		// Prints out the set size (# of unique numbers)
		System.out.println(ts.size());
		
		// Print in sorted order.
		System.out.println("here are all the values");
		for (Integer x: ts)
			System.out.println(x);
		
		// How to remove smallest.
		int min = ts.pollFirst();
		System.out.println("removed "+min+" now has "+ts.size()+" values");
		
		// These methods are really useful.
		int gt50 = ts.higher(50);
		int lt50 = ts.lower(50);
		System.out.println("smallest > 50 is "+gt50);
		System.out.println("largest < 50 is "+lt50);
	}
	
	// Showing the use of a TreeMap
	public static void testTreeMap() {
		
		// Set it up.
		Scanner stdin = new Scanner(System.in);
		TreeMap<String,Integer> map = new TreeMap<String,Integer>();
		int n = stdin.nextInt();
		
		// Read n names.
		for (int i=0; i<n; i++) {
			String name = stdin.next();
			
			// Not in the map, put it.
			if (!map.containsKey(name))
				map.put(name, 0);
			
			// Add in the vote for name.
			map.put(name, map.get(name)+1);
		}
		
		// Prints results in Alpha order.
		for (String name : map.keySet())
			System.out.println(name+"\t"+map.get(name));
	}
}