405349: GYM101911 F Tickets

Last $$$n$$$ days Monocarp used public transport to get to the university. He received a ticket with number $$$t_i$$$ during the $$$i$$$-th day.

Tickets' numbers are six digit non-negative integers with possible leading zeroes. For example, $$$123456$$$, $$$000000$$$, $$$099999$$$, $$$999999$$$ are correct ticket numbers, but $$$1234567$$$, $$$12345$$$, $$$9$$$ are not. Every day tickets are numbered from zero. The first passenger gets ticket number $$$000000$$$, the second one — ticket number $$$000001$$$, the third one — number $$$000002$$$ and so on every day. Assume that each day the number of passengers doesn't exceed $$$10^6$$$.

Unluckiness of the ticket is equal to absolute difference between the sum of the first three digits and the sum of the last three. For example, unluckiness of the ticket number $$$345123$$$ is equal to $$$|(3 + 4 + 5) - (1 + 2 + 3)| = 6$$$, or unluckiness of the ticket number $$$238526$$$ is equal to $$$|(2 + 3 + 8) - (5 + 2 + 6)| = 0$$$.

One passenger is luckier than other if unluckiness of first passenger's ticket is strictly less than unluckiness of the second one's ticket.

For each of $$$n$$$ days for given Monocarp's ticket's number $$$t_i$$$ calculate the number of passengers who received their tickets before him during this day and are luckier than Monocarp.

Examine examples for the further understanding of the statement.

The first line contains one integer $$$n$$$ $$$(1 \le n \le 2\cdot10^{5})$$$ — the number of days during which Monocarp used public transport.

Each of the next $$$n$$$ lines contains one six digit integer $$$t_i$$$ ($$$0 \le t_i < 10^6$$$, $$$t_i$$$ can have leading zeroes) — the ticket Monocarp received during the corresponding day.

Print $$$n$$$ lines: one integer per line — the number of passengers who received their tickets before Monocarp during the corresponding day and are luckier than Monocarp.

5
001000
000000
999000
453234
654331

1
0
998999
121496
470362

During the first day the only one passenger who got ticket before Monocarp was luckier. This passenger got ticket number $$$000000$$$.

During the second day Monocarp was the first one, so there was nobody before him.

During the third day all passengers except one who got tickets before Monocarp were more luckier than him. The one whose unluckiness was equal to Monocarp's unluckiness got ticket number $$$000999$$$.