// By Desi QnA
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};
        int[] b = new int[10];
        int i = 0;
        while (i < n) {
            int x = a[i];
            b[x]++;
            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[x]); // takes O(1) time..
            System.out.print(' ');
            j++;
        }
        // Above for loop took O(q) time.
 
        // Hence total time: O(n+q).
    }
}
 

Ly8gQnkgRGVzaSBRbkEKaW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludCBuID0gOTsKICAgICAgICBpbnRbXSBhID0gezEsIDMsIDMsIDQsIDEsIDQsIDQsIDQsIDR9OwogICAgICAgIGludFtdIGIgPSBuZXcgaW50WzEwXTsKICAgICAgICBpbnQgaSA9IDA7CiAgICAgICAgd2hpbGUgKGkgPCBuKSB7CiAgICAgICAgICAgIGludCB4ID0gYVtpXTsKICAgICAgICAgICAgYlt4XSsrOwogICAgICAgICAgICBpKys7CiAgICAgICAgfQogICAgICAgIC8vIEFib3ZlIGZvciBsb29wIHRvb2sgTyhuKSB0aW1lLgogICAgICAgIC8vIEFsbCBmcmVxdWVuY2llcyBoYXZlIGJlZW4gY2FsY3VsYXRlZCBpbiBhZHZhbmNlIGJ5IG5vdy4uIDotKSA6LSkKCiAgICAgICAgaW50W10gcXVlcmllcyA9IHszLCA0LCAxfTsKICAgICAgICBpbnQgcSA9IDM7CiAgICAgICAgaW50IGogPSAwOwogICAgICAgIHdoaWxlIChqIDwgcSkgewogICAgICAgICAgICBpbnQgeCA9IHF1ZXJpZXNbal07CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoYlt4XSk7IC8vIHRha2VzIE8oMSkgdGltZS4uCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoJyAnKTsKICAgICAgICAgICAgaisrOwogICAgICAgIH0KICAgICAgICAvLyBBYm92ZSBmb3IgbG9vcCB0b29rIE8ocSkgdGltZS4KCiAgICAgICAgLy8gSGVuY2UgdG90YWwgdGltZTogTyhuK3EpLgogICAgfQp9Cg==