You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

给你一个由 $n$ 个正整数组成的数组 $a$ 和一个分数。如果你的分数大于或等于 $a_i$，那么你可以将分数增加 $a_i$，并从数组中删除 $a_i$。

对于每个索引 $i$，如果您删除了 $a_i$，并将分数设置为 $a_i$，则输出您可以删除的额外数组元素的最大数量。请注意，移除 $a_i$ 不应计入答案中。

Format

Input

第一行包含一个整数 $n$ ($1 \le n \le 10^5$) - 数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) - 数组的元素。

Output

输出 $n$ 个整数，其中第 $i$ 个整数表示如果从数组中删除 $a_i$ 并将分数设置为 $a_i$后，可以删除的额外数组元素的最大数量。

Samples

5
20 5 1 4 2

4 3 0 3 1 

Limitation

1s, 1024KiB for each test case.