MCHAOS - Chaos Strings


English Vietnamese

 

Little Lovro likes to play games with words. During the last few weeks he realized that some words don't like each other.


The words A and B don't like each other if the word A is lexicographically before the word B, but the word B' is lexicographically before the word A', where X' stands for the word X reversed (if X="kamen" then X'="nemak"). For example, the words "lova" and "novac" like each other, but the words "aron" and "sunce" don't like each other.

Given some set of the words, we define  the degree of chaos of the set as  the number of pairs of different words that don't like each other.

Write a program that, given a set of words, finds the chaos degree for the set.

 

Input

 

The first line of input contains an integer N, 2 ≤ N ≤ 100 000.

Each of the following N lines contains one word – a sequence of at most 10 lowercase letters of the English alphabet ('a'-'z'). There will be no two identical words in the set.

 

Output

 

The first and only line of output should contain a single integer – the chaos degree of the given set of words.


Note: use 64-bit signed integer type (int64 in Pascal, long long in 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


hide comments
TP: 2016-07-20 11:51:37

Learnt more about hashing!!! Nice I/o optimisation problem.

MyCodeBattle: 2015-10-04 15:19:20

Don't use any STL and you'll succeed.
But I think it's meaningless...

Baojun Wang: 2015-07-30 00:49:34

No accepted solution except c/c++/fpc, relax the time limit to allow other languages, please.

sebinechita: 2015-07-12 15:22:34

One cool solution is converting the strings in long long variables :)

Ishant : 2014-12-29 18:07:33

very easy :) Don't use STL .

Archit Jain: 2014-12-25 20:19:10

seems easy
but time limit is too strict

Vedran Kurdija: 2014-03-25 18:48:48

pointless time limit

Last edit: 2014-03-25 18:51:37
Suman: 2014-01-25 08:39:19

I make it AC after knowing how to copy a C string to C++ string....... :D
Hope, it will help you. (Y)

Venkatesh Ganesan: 2013-12-26 12:42:48

TLE. crazy IO optimization => AC.

BLANKRK: 2013-12-08 18:10:50

done!!! :)


Added by:~!(*(@*!@^&
Date:2009-06-06
Time limit:0.152s-0.219s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 06