KAOS - Kaos


kaos


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 data


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 data


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++)


examples


input                                          input                                       input


2                                                  4                                             14

lopta                                           lova                                          branimir

kugla                                          novac                                       vladimir

                                                  aron                                          tom

output                                       sunce                                        kruz

0                                                                                                  bred

                                                  output                                       pit

                                                  3                                                zemlja

                                                                                                    nije

                                                                                                   ravna

                                                                                                  ploca

                                                                                                  ko

                                                                                                  je

                                                                                                   zapalio

                                                                                                   zito


                                                                                                 output

                                                                                                    48


hide comments
learnerinblack: 2018-06-07 14:49:24

When you are the 100th buddy to solve this question.
AC in one go :D mergesort did it's work!

Filip K. Dosilovic: 2015-10-29 14:12:03

@mehmetinal @cricycle problem was added because time limit on MCHAOS is not official time limit for the problem

Alex Anderson: 2015-10-27 04:38:51

@mehmetin, you're right. I think this problem should be removed.

mehmetin: 2015-10-06 11:20:18

This problem is the exact duplicate of MCHAOS. Only difference is the relaxed time limit.

Last edit: 2015-10-06 11:25:33
matematikaadit: 2015-09-30 16:24:14

a copy-paste-friendly version of examples above:

2
lopta
kugla

4
lova
novac
aron
sunce

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

Filip K. Dosilovic: 2015-09-21 21:01:27

@SRC: no, there is no space.

Last edit: 2015-09-28 18:41:18
SRC: 2015-09-19 17:15:59

is that a space before lova and novac in the 2nd example?

miodziu: 2015-09-18 10:25:47

@ravi12345: Empty words are not allowed.

miodziu: 2015-09-18 10:22:00

My ACC solution gives result 47 in 3rd example. Also my brute-force algorithm gives 47 in this example :)

ravi12345: 2015-09-18 08:26:32

empty words are allowed or not?


Added by:Filip Karlo Došilović
Date:2015-09-17
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC COFFEE DART FORTH GOSU JS-MONKEY KTLN OCT PROLOG R RACKET SQLITE SWIFT UNLAMBDA
Resource:COI, 2006, 2nd Day, Seniors