import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        int n = 9;
        int[] a = {1,3,3,4,1,4,4,4,4}; // array
        HashMap<Integer,Integer> b = new HashMap<>(); // hashmap
        int i = 0;
        while(i<n)
        {
            int x = a[i];
            b.put(x, b.getOrDefault(x, 0) + 1);
            i++;
        }
        //Above for loop took O(n) time.
        //All frequencies have been calculated in advance by now.. :-) :-)
 
        int[] queries = {3,4,1};
        int q = 3;
        int j = 0;
        while(j<q)
        {
            int x = queries[j];
            System.out.print(b.getOrDefault(x, 0) + " "); //takes O(1) time..
            j++;
        }
        //Above for loop took O(q) time.
 
        //Hence total time : O(n+q).
    }
}
 

aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludCBuID0gOTsKICAgICAgICBpbnRbXSBhID0gezEsMywzLDQsMSw0LDQsNCw0fTsgLy8gYXJyYXkKICAgICAgICBIYXNoTWFwPEludGVnZXIsSW50ZWdlcj4gYiA9IG5ldyBIYXNoTWFwPD4oKTsgLy8gaGFzaG1hcAogICAgICAgIGludCBpID0gMDsKICAgICAgICB3aGlsZShpPG4pCiAgICAgICAgewogICAgICAgICAgICBpbnQgeCA9IGFbaV07CiAgICAgICAgICAgIGIucHV0KHgsIGIuZ2V0T3JEZWZhdWx0KHgsIDApICsgMSk7CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9CiAgICAgICAgLy9BYm92ZSBmb3IgbG9vcCB0b29rIE8obikgdGltZS4KICAgICAgICAvL0FsbCBmcmVxdWVuY2llcyBoYXZlIGJlZW4gY2FsY3VsYXRlZCBpbiBhZHZhbmNlIGJ5IG5vdy4uIDotKSA6LSkKCiAgICAgICAgaW50W10gcXVlcmllcyA9IHszLDQsMX07CiAgICAgICAgaW50IHEgPSAzOwogICAgICAgIGludCBqID0gMDsKICAgICAgICB3aGlsZShqPHEpCiAgICAgICAgewogICAgICAgICAgICBpbnQgeCA9IHF1ZXJpZXNbal07CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoYi5nZXRPckRlZmF1bHQoeCwgMCkgKyAiICIpOyAvL3Rha2VzIE8oMSkgdGltZS4uCiAgICAgICAgICAgIGorKzsKICAgICAgICB9CiAgICAgICAgLy9BYm92ZSBmb3IgbG9vcCB0b29rIE8ocSkgdGltZS4KCiAgICAgICAgLy9IZW5jZSB0b3RhbCB0aW1lIDogTyhuK3EpLgogICAgfQp9Cg==