01204212/id request

This is part of 01204212

An API requires every user to have a unique ID. To ensure that it provides an interface to check and allocate IDs. There are N requests; each request specifies an ID x, which is an integer from 0 up to 1,000,000,000. For each request, your program have to answer if x has been used. In the case where x is new, it allocates that integer for the requested user. Initially, no ID has been used.

Input

• First line: an integer N (1<=N<=100,000)
• The next N lines: each line contains an integer x

Output

There are N lines of output, each contains either Y (if the requested ID has been used before) or N (if the requested ID is new)

Example

Input

10
4
2
4
10
100
30
10
35
100
200

Output

N
N
Y
N
N
N
Y
N
Y
N

Test data

Download at: here

Solution to n10.in

N
N
N
N
N
N
N
Y
N
Y

Solution to n1000.in (first 20 lines)

N
N
N
N
N
Y
N
N
N
N
N
Y
Y
N
Y
N
Y
Y
N
N

Code

Collection choices

• TreeSet
• HashSet
• Implementation of "static" sets with binary search

Main method

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    int n;
    int[] xs;
    
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        
        m.readInput();
        m.process();
    }

    private void process() {    
        // your code here
    }
    
    private void readInput() throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        n = Integer.parseInt(reader.readLine());
        xs = new int[n];

        for(int i=0; i<n; i++) {
            xs[i] = Integer.parseInt(reader.readLine());
        }

    }
}