Coalition PROG1119

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    pair<int,int> arr[n];
    int qs[n+1];qs[n] = 0;
    int sumall = 0;
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&arr[i].first);
        arr[i].second = i;
        sumall += arr[i].first;
    }
    sort(arr,arr+n);
/*  printf("Array\n Data : ");
    for(int i = 0 ; i < n ; i++){
        printf("%d ",arr[i].first);
    }
    printf("\n Index : ");
    for(int i = 0 ; i < n ; i++){
        printf("%d ",arr[i].second);
    }
    printf("\n\nQuicksum\n Data : ");*/
    for(int i = n - 1 ; i >= 0 ; i--){
        qs[i] = qs[i+1] + arr[i].first;
    }
/*  for(int i = 0 ; i < n ; i++){
        printf("%d ",qs[i]);
    }
    printf("\n");*/

    int ans[n];
    for(int i = 0 ; i < n ; i++){ //calculation
        int l = 0 , r = n - 1;
        int mina = n - 1;
        while(l <= r){
            int m = (l+r)/2;
            int sum = arr[i].first + qs[m];
            if(m <= i){
                sum -= arr[i].first;
            }
            if(sum > sumall/2){
                int lenght = n - m;
                if(m <= i){
                    lenght--;
                }
                if(lenght < mina)mina = lenght;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        ans[arr[i].second] = mina;
    }
    for(int i = 0 ; i < n ; i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}