Hyunju and Yunju's Fun Word Game

Time limit1sMemory limit128 MB

Summary

Count unordered word pairs (A,B) where A<B lexicographically but reverse(B)<reverse(A), given up to 100,000 distinct words.

Level: Medium6 of 10
Topics: Sorting, String, Binary search, Divide and conquer
Solved: No attempts yet

Problem

Hyunju and Yunju spend Sundays playing a word game. While playing, they noticed that some pairs of words do not like each other.

For two words A and B, suppose A comes before B in lexicographic order. If B' comes before A' in lexicographic order, then the two words do not like each other. Here X' means the word X written in reverse. For instance, if X = "kamen", then X' = "nemak".

For instance, "lova" and "novac" like each other, while "aron" and "sunce" do not like each other.

Given a list of words, write a program that counts how many unordered pairs of words do not like each other.

Input

The first line contains the number of words N (2 <= N <= 100,000).

Each of the next N lines contains one word. Every word consists only of lowercase English letters and has length at most 10. No word appears more than once.

Output

Print one integer: the number of pairs of input words that do not like each other.

Examples3

Example 1
Input
```
4
lova
novac
aron
sunce
```
Expected output
```
3
```
Example 2
Input
```
2
lopta
kugla
```
Expected output
```
0
```

Example 3

Input

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

Expected output