#include<stdio.h>
#include<stdlib.h>
#include<inttypes.h>
#include<stdbool.h>
#include<string.h>
#include<assert.h>

#define MAX_VAL 1000000

struct multiples_array {
    uint32_t value;
    uint32_t no_of_multiples;
};
typedef struct multiples_array multiples_array_t;

void take_input(multiples_array_t *const,uint32_t);
void generate_multiples(multiples_array_t *const,uint32_t);
const uint32_t find_maximum(multiples_array_t *const,uint32_t);

int main(void) {
    uint32_t n;
    printf("Enter the size of the array\n");
    scanf("%"SCNu32,&n);
    assert(n > 0 && n < 100001);
    multiples_array_t *const data = calloc(n,sizeof(multiples_array_t));
    if(data) {
        take_input(data,n);
        generate_multiples(data,n);
        free(data);
    } else {
        fprintf(stderr,"Memory not allocated to *data pointer!\n");
    }
    return 0;
}

void take_input(multiples_array_t *const data,uint32_t n) {
    for(uint32_t i = 0; i < n; ++i) {
        scanf("%"SCNu32,&(data[i].value));
        data[i].no_of_multiples = 0;
        assert((data[i].value) > 0 && (data[i].value) < (MAX_VAL + 1));
    }
}

void generate_multiples(multiples_array_t *const data,uint32_t n) {
    uint32_t *const freq_data = calloc(MAX_VAL,sizeof(uint32_t));
    /*  Iterating through each a[i] and before increamenting the freq[i], finding out how many multiples of a[i] I have encountered till now by parsing the freq_data[] upto the max_val.
    */
    if(freq_data) {
        uint32_t max_val = 0;
        for(uint32_t i = 0; i < n; ++i) {
            if((data[i].value) > max_val) {
                max_val = data[i].value;
            }
            if(data[i].value == 1) {
                data[i].no_of_multiples = i;
            } else if(data[i].value == max_val) {
                data[i].no_of_multiples += freq_data[max_val - 1];
            } else if(data[i].value <= max_val) {
                for(uint32_t j = 1; ((data[i].value) * j) <= max_val; ++j) {
                    (data[i].no_of_multiples) += freq_data[((data[i].value) * j) - 1];
                }
            }
            ++freq_data[(data[i].value) - 1];
        }
        for(uint32_t i = 0; i < n; ++i) {
            printf("%"PRIu32" ",(data[i].no_of_multiples));
        }
        printf("\n");
        free(freq_data);
    } else {
        fprintf(stderr,"Memory not allocated to *freq_data pointer!\n");
    }
}

const uint32_t find_maximum(multiples_array_t *const data,uint32_t n) {
    uint32_t max = 0;
    for(uint32_t i = 0; i < n; ++i) {
        if((data[i].value) > max) {
            max = data[i].value;
        }
    }
    return max;
}