appeal

Problem Description

Guan is trying to pursue a degree in English Literature. Since Guan is horrible at ELit, he is trying to write a letter of appeal to the University in order to apply for the degree. Guan, being horribly uncreative, only has N words in his appeal letter and all these N words are made of small letters that are less than 10 characters long, seperated by only spaces and without punctuation.

However, Guan knows something most people don't about the system. He knows that the machine that takes in the letters of appeal and rates them by a "reliability" rating. This reliability rating is the number of "reliable" word pairs there are in the letter.

A pair of words i and j are reliable if and only if word i is lexicographically smaller than word j and i < j. For example, ("apple", "bear") is reliable, ("aeroplane", "apple") is reliable and ("bear, banana") is not.

Guan writes out a letter and prepares it to submit it to the University. Help Guan calculate its "reliability" rating.

Subtasks

Subtask 1 (14%): 1 ≤ N ≤ 100. The words will not be more than 5 letters long.
Subtask 2 (25%): 1 ≤ N ≤ 100.
Subtask 3 (28%): 1 ≤ N ≤ 1000.
Subtask 4 (33%): 1 ≤ N ≤ 100000.

Input

The first line of input will contain one integer, N.
The next line of input will contain N words, as mentioned above.

Output

The output should consist of one line, stating the reliability rating of the letter.

Sample Input

5
i really love apple pies

Sample Output

5

Explanation

(i, really), (i, love), (i, pies), (love, pies), (apple, pies) are "reliable" word pairs.