시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 160 41 30 41.096%

문제

현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다.

두 단어 A와 B가 있을 때, A가 B보다 사전순으로 앞서는데, B'가 A' 보다 사전 순으로 앞서면, 두 단어는 서로 좋아하지 않는다. 여기서 X'는 단어 X를 뒤집은 것을 말한다. (X = "kamen"이면, X'는 "nemak" 이다)

에를 들어, "lova"와 "novac"은 서로 좋아하고, "aron"과 "sunce"는 서로 좋아하지 않는다.

단어의 목록이 주어졌을 때, 서로 좋아하지 않는 단어의 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N개의 줄에는 한 줄에 하나씩 단어가 주어진다. 단어는 영어 알파벳 소문자로만 이루어져 있으며, 길이는 10개를 넘지 않는다. 같은 단어가 두 번 이상 주어지는 경우는 없다.

출력

첫재 줄에 입력으로 주어진 단어 중에서 서로 좋아하지 않는 쌍의 개수를 출력한다. 

예제 입력 1

4
lova
novac
aron
sunce

예제 출력 1

3

예제 입력 2

2
lopta
kugla

예제 출력 2

0

예제 입력 3

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

예제 출력 3

48
W3sicHJvYmxlbV9pZCI6IjMxNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MDRcdWM4ZmNcdWM2NDAgXHVjNzI0XHVjOGZjXHVjNzU4IFx1YzdhY1x1YmJmOFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWM4ZmNcdWM2NDAgXHVjNzI0XHVjOGZjXHViMjk0IFx1Yzc3Y1x1YzY5NFx1Yzc3Y1x1YjljOFx1YjJlNCBcdWM3YWNcdWJiZjhcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWJhNzRcdWMxMWMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YmNmNFx1YjBiOFx1YjJlNC4gXHViMmU4XHVjNWI0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWIzNTggXHVjOTExLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWIyZThcdWM1YjQgQVx1YzY0MCBCXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIEFcdWFjMDAgQlx1YmNmNFx1YjJlNCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNTVlXHVjMTFjXHViMjk0XHViMzcwLCBCJiMzOTtcdWFjMDAgQSYjMzk7IFx1YmNmNFx1YjJlNCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YmE3NCwgXHViNDUwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVjODhiXHVjNTQ0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFgmIzM5O1x1YjI5NCBcdWIyZThcdWM1YjQgWFx1Yjk3YyBcdWI0YTRcdWM5ZDFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gKFggPSAmcXVvdDtrYW1lbiZxdW90O1x1Yzc3NFx1YmE3NCwgWCYjMzk7XHViMjk0ICZxdW90O25lbWFrJnF1b3Q7IFx1Yzc3NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjNWQwXHViOTdjIFx1YjRlNFx1YzViNCwgJnF1b3Q7bG92YSZxdW90O1x1YzY0MCAmcXVvdDtub3ZhYyZxdW90O1x1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjODhiXHVjNTQ0XHVkNTU4XHVhY2UwLCAmcXVvdDthcm9uJnF1b3Q7XHVhY2ZjICZxdW90O3N1bmNlJnF1b3Q7XHViMjk0IFx1YzExY1x1Yjg1YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzExY1x1Yjg1YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM2MDFcdWM1YjQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMTBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWMxMWNcdWI4NWMgXHVjODhiXHVjNTQ0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia2FvcyIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIExvdnJvIGxpa2VzIHRvIHBsYXkgZ2FtZXMgd2l0aCB3b3Jkcy4gRHVyaW5nIHRoZSBsYXN0IGZldyB3ZWVrcyBoZSByZWFsaXplZCB0aGF0IHNvbWUgd29yZHMgZG9uJiMzOTt0IGxpa2UgZWFjaCBvdGhlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHdvcmRzIEEgYW5kIEIgZG9uJiMzOTt0IGxpa2UgZWFjaCBvdGhlciBpZiB0aGUgd29yZCBBIGlzIGxleGljb2dyYXBoaWNhbGx5IGJlZm9yZSB0aGUgd29yZCBCLCBidXQgdGhlIHdvcmQgQiYjMzk7IGlzIGxleGljb2dyYXBoaWNhbGx5IGJlZm9yZSB0aGUgd29yZCBBJiMzOTssIHdoZXJlIFgmIzM5OyBzdGFuZHMgZm9yIHRoZSB3b3JkIFggcmV2ZXJzZWQgKGlmIFg9JnF1b3Q7a2FtZW4mcXVvdDsgdGhlbiBYJiMzOTs9JnF1b3Q7bmVtYWsmcXVvdDspLiBGb3IgZXhhbXBsZSwgdGhlIHdvcmRzICZxdW90O2xvdmEmcXVvdDsgYW5kICZxdW90O25vdmFjJnF1b3Q7IGxpa2UgZWFjaCBvdGhlciwgYnV0IHRoZSB3b3JkcyAmcXVvdDthcm9uJnF1b3Q7IGFuZCAmcXVvdDtzdW5jZSZxdW90OyBkb24mIzM5O3QgbGlrZSBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBzb21lIHNldCBvZiB0aGUgd29yZHMsIHdlIGRlZmluZSB0aGUgZGVncmVlIG9mIGNoYW9zIG9mIHRoZSBzZXQgYXMgdGhlIG51bWJlciBvZiBwYWlycyBvZiBkaWZmZXJlbnQgd29yZHMgdGhhdCBkb24mIzM5O3QgbGlrZSBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYSBzZXQgb2Ygd29yZHMsIGZpbmRzIHRoZSBjaGFvcyBkZWdyZWUgZm9yIHRoZSBzZXQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMTAwIDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgb25lIHdvcmQgJm5kYXNoOyBhIHNlcXVlbmNlIG9mIGF0IG1vc3QgMTAgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQgKCYjMzk7YSYjMzk7LSYjMzk7eiYjMzk7KS4gVGhlcmUgd2lsbCBiZSBubyB0d28gaWRlbnRpY2FsIHdvcmRzIGluIHRoZSBzZXQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgJm5kYXNoOyB0aGUgY2hhb3MgZGVncmVlIG9mIHRoZSBnaXZlbiBzZXQgb2Ygd29yZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHVzZSA2NC1iaXQgc2lnbmVkIGludGVnZXIgdHlwZSAoaW50NjQgaW4gUGFzY2FsLCBsb25nIGxvbmcgaW4gQ1wvQysrKS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=