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

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 {

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        int n = Integer.parseInt(reader.readLine());
            
        for(int i=0; i<n; i++) {
            int x = Integer.parseInt(reader.readLine());
            // do something
        }
    }
}