Chuỗi Đẹp

Trong một buổi họp chiến lược, giám đốc đã đưa ra một bài toán thú vị cho FullHouse Dev. Bài toán liên quan đến việc tính toán giá trị đẹp của các chuỗi, một khái niệm mà công ty đang xem xét áp dụng cho sản phẩm mới. FullHouse Dev được giao nhiệm vụ phát triển thuật toán để giải quyết vấn đề này.

Bài toán

Có \(N\) chuỗi đẹp và cần tính giá trị đẹp của mỗi chuỗi. Giá trị đẹp của chuỗi ở vị trí \(i\) được định nghĩa là số lượng chuỗi có vị trí nhỏ hơn \(i\) mà nhỏ hơn chuỗi \(i\) theo thứ tự từ điển.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(N\) - số lượng chuỗi đẹp.
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm các chữ cái tiếng Anh viết thường.

OUTPUT FORMAT:

• In ra \(N\) dòng, mỗi dòng chứa một số nguyên biểu thị giá trị đẹp của chuỗi tương ứng.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq |A_i| \leq 10\), trong đó \(|A_i|\) là độ dài của chuỗi thứ \(i\).

Ví dụ

INPUT

4
a
c
d
b

OUTPUT

0
1
2
1

Giải thích

• Giá trị đẹp của "a": 0 (không có chuỗi nào nhỏ hơn "a")
• Giá trị đẹp của "c": 1 (chỉ có "a" nhỏ hơn "c")
• Giá trị đẹp của "d": 2 (cả "a" và "c" đều nhỏ hơn "d")
• Giá trị đẹp của "b": 1 (chỉ có "a" nhỏ hơn "b")

FullHouse Dev đã rất hứng thú với bài toán này và quyết tâm phát triển một giải pháp hiệu quả để tính toán giá trị đẹp cho tất cả các chuỗi, nhằm đáp ứng yêu cầu của giám đốc và góp phần vào sự phát triển của sản phẩm mới.