MCHAOS - Chaos Strings

English Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mchaos


Lovro thích chơi với các từ và nhận thấy một số từ có vẻ không thích nhau.


Hai từ A và B không thích nhau nếu A đứng trước B (thứ tự từ điển), nhưng B' lại đứng trước A', với X' từ viết ngược của X (ví dụ X="kamen" thì X'="nemak"). VD, hai từ "lova" và "novac" thích nhau, nhưng hai từ "aron" và "sunce" thì không.

Cho một tập các từ, ta định nghĩa mức hỗn loạn của tập là số cặp từ không thích nhau.

Tính số cặp này.

Input

Dòng đầu là số nguyên N, 2 ≤ N ≤ 100 000.

Sau đó N dòng chứa các từ, mỗi từ có nhiều nhất 10 chữ cái thường, 'a'-'z'. Không có 2 từ giống nhau.

Output

Mức hỗn loạn của tập từ này.

Kết quả là số 64 bit  (int64 với Pascal, long long với C/C++).

Sample

input 
 
2
lopta
kugla
 
output
 
0

input
 
4
lova
novac
aron
sunce
 
output
 
3

input
 
14
branimir
vladimir
tom
kruz
bred
pit
zemlja
nije
ravna
ploca
ko
je
zapalio
zito
 
output
 
48


Added by:psetter
Date:2009-06-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 06

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.