시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 73 40 33 55.000%

문제

이것은 존이 농장을 개편하기 전의 이야기이다.

존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다.

이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 N마리고, 1, 2, ..., N이라는 번호가 붙는다. (원래 A부터 Z까지 이름이 있었는데, 소가 많아지면서 더 이상 그 방법을 사용할 수 없게 되었다.) 존은 2N개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 길이 2N의 수열에는 각 번호가 두 번씩 나타날 것이다.

어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.

입력

첫 줄에 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 2N줄에는 한 줄에 하나씩 길 위의 점을 지나간 소의 번호가 주어진다.

출력

경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

예제 입력 1

4
3
2
4
4
1
3
2
1

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE0NDYzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NFx1YWM4M1x1Yzc0MCA8YSBocmVmPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTQ0NjZcIj5cdWM4NzRcdWM3NzQgXHViMThkXHVjN2E1XHVjNzQ0IFx1YWMxY1x1ZDNiODxcL2E+XHVkNTU4XHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWM3NzRcdWM1N2NcdWFlMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDBcdWIyOTQgXHVjNmQwXHVkNjE1IFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWRmOCBcdWI0NThcdWI4MDhcdWM1ZDAgXHVhZTM4XHVjNzc0IFx1YjQ1OFx1YjdlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzg3NFx1Yzc1OCBcdWMxOGNcdWIyOTQgXHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OCBcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YWMwMCBcdWQ0ODBcdWM3NDQgXHViYTM5XHVhY2UwIFx1YzgwMFx1YjE0MVx1YzVkMCBcdWIyZTRcdWMyZGMgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YWMwMCBcdWQ1ZGJcdWFjMDRcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjMThjXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMyYjVcdWFkMDBcdWIzMDBcdWI4NWMgXHViOWU0XHVjNzdjIFx1YjYxMVx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwY1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzE4Y1x1YjI5NCBcdWM2ZDBcdWQ2MTUgXHVhZTM4XHVjNzU4IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWQ1NWMgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWM4MTBcdWM3NDQgXHVjOWMwXHViMDk4IFx1YjA5OFx1YWMwNFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWMxOGNcdWIzYzQgXHVhZTM4IFx1YzcwNFx1Yzc1OCBcdWFjMTlcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YWM3OCBcdWM5YzBcdWNmMWNcdWJjZjggXHVjODc0XHVjNzQwIFx1Yzc3NCBcdWM4MTBcdWI0ZTRcdWM3NDQgXHViZDg0XHVjMTFkXHVkNTc0IFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzE4Y1x1YjI5NCBcdWNkMWQgTlx1YjljOFx1YjlhY1x1YWNlMCwgMSwgMiwgLi4uLCBOXHVjNzc0XHViNzdjXHViMjk0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWIyOTRcdWIyZTQuIChcdWM2ZDBcdWI3OTggPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzE0NDY4XCI+QVx1YmQ4MFx1ZDEzMCBaXHVhZTRjXHVjOWMwPFwvYT4gXHVjNzc0XHViOTg0XHVjNzc0IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YjM3MCwgXHVjMThjXHVhYzAwIFx1YjljZVx1YzU0NFx1YzljMFx1YmE3NFx1YzExYyBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YWRmOCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LikgXHVjODc0XHVjNzQwIDJOXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc0NCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViY2Y0XHViYTc0XHVjMTFjIFx1YWMwMSBcdWM4MTBcdWM3NDQgXHVjNWI0XHViNWE0IFx1YzE4Y1x1YWMwMCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTRcdWM5YzAgXHVhZTMwXHViODVkXHVkNTg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0IFx1YjBiOCBcdWFlMzhcdWM3NzQgMk5cdWM3NTggXHVjMjE4XHVjNWY0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJjODhcdWQ2MzhcdWFjMDAgXHViNDUwIFx1YmM4OFx1YzUyOSBcdWIwOThcdWQwYzBcdWIwYTAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHViNDUwIFx1YzE4Y1x1YjI5NCBcdWM1YjRcdWI1YTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM3N1x1YjRlMCBcdWFkZjggXHVhY2JkXHViODVjXHVhYzAwIFx1YzViNFx1YjUxOFx1YWMwMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWM1N2MgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWMxOGNcdWFjMDAgXHVjZDFkIFx1YmE4NyBcdWMzMGRcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiAoMSAmbGU7IE4gJmxlOyA1MCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDJOXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWUzOCBcdWM3MDRcdWM3NTggXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwNCBcdWMxOGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjYmRcdWI4NWNcdWFjMDAgXHViYjM0XHVjODcwXHVhYzc0IFx1YjljY1x1YjA5OFx1YjI5NCBcdWMxOGNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTQ0NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaHkgRGlkIHRoZSBDb3cgQ3Jvc3MgdGhlIFJvYWQgSUlJIChHb2xkKSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxheW91dCBvZiBGYXJtZXIgSm9obiYjMzk7cyBmYXJtIGlzIHF1aXRlIHBlY3VsaWFyLCB3aXRoIGEgbGFyZ2UgY2lyY3VsYXIgcm9hZCBydW5uaW5nIGFyb3VuZCB0aGUgcGVyaW1ldGVyIG9mIHRoZSBtYWluIGZpZWxkIG9uIHdoaWNoIGhpcyBjb3dzIGdyYXplIGR1cmluZyB0aGUgZGF5LiBFdmVyeSBtb3JuaW5nLCB0aGUgY293cyBjcm9zcyB0aGlzIHJvYWQgb24gdGhlaXIgd2F5IHRvd2FyZHMgdGhlIGZpZWxkLCBhbmQgZXZlcnkgZXZlbmluZyB0aGV5IGFsbCBjcm9zcyBhZ2FpbiBhcyB0aGV5IGxlYXZlIHRoZSBmaWVsZCBhbmQgcmV0dXJuIHRvIHRoZSBiYXJuLjxcL3A+XHJcblxyXG48cD5BcyB3ZSBrbm93LCBjb3dzIGFyZSBjcmVhdHVyZXMgb2YgaGFiaXQsIGFuZCB0aGV5IGVhY2ggY3Jvc3MgdGhlIHJvYWQgdGhlIHNhbWUgd2F5IGV2ZXJ5IGRheS4gRWFjaCBjb3cgY3Jvc3NlcyBpbnRvIHRoZSBmaWVsZCBhdCBhIGRpZmZlcmVudCBwb2ludCBmcm9tIHdoZXJlIHNoZSBjcm9zc2VzIG91dCBvZiB0aGUgZmllbGQsIGFuZCBhbGwgb2YgdGhlc2UgY3Jvc3NpbmcgcG9pbnRzIGFyZSBkaXN0aW5jdCBmcm9tIGVhY2gtb3RoZXIuIEZhcm1lciBKb2huIG93bnMmbmJzcDtOTiZuYnNwO2Nvd3MsIGNvbnZlbmllbnRseSBpZGVudGlmaWVkIHdpdGggdGhlIGludGVnZXIgSURzJm5ic3A7MSZoZWxsaXA7Tiwgc28gdGhlcmUgYXJlIHByZWNpc2VseSZuYnNwOzJOMk4mbmJzcDtjcm9zc2luZyBwb2ludHMgYXJvdW5kIHRoZSByb2FkLiBGYXJtZXIgSm9obiByZWNvcmRzIHRoZXNlIGNyb3NzaW5nIHBvaW50cyBjb25jaXNlbHkgYnkgc2Nhbm5pbmcgYXJvdW5kIHRoZSBjaXJjbGUgY2xvY2t3aXNlLCB3cml0aW5nIGRvd24gdGhlIElEIG9mIHRoZSBjb3cgZm9yIGVhY2ggY3Jvc3NpbmcgcG9pbnQsIHVsdGltYXRlbHkgZm9ybWluZyBhIHNlcXVlbmNlIHdpdGgmbmJzcDsyTiBudW1iZXJzIGluIHdoaWNoIGVhY2ggbnVtYmVyIGFwcGVhcnMgZXhhY3RseSB0d2ljZS4gSGUgZG9lcyBub3QgcmVjb3JkIHdoaWNoIGNyb3NzaW5nIHBvaW50cyBhcmUgZW50cnkgcG9pbnRzIGFuZCB3aGljaCBhcmUgZXhpdCBwb2ludHMuPFwvcD5cclxuXHJcbjxwPkxvb2tpbmcgYXQgaGlzIG1hcCBvZiBjcm9zc2luZyBwb2ludHMsIEZhcm1lciBKb2huIGlzIGN1cmlvdXMgaG93IG1hbnkgdGltZXMgdmFyaW91cyBwYWlycyBvZiBjb3dzIG1pZ2h0IGNyb3NzIHBhdGhzIGR1cmluZyB0aGUgZGF5LiBIZSBjYWxscyBhIHBhaXIgb2YgY293cyZuYnNwOyhhLGIpJm5ic3A7YSAmcXVvdDtjcm9zc2luZyZxdW90OyBwYWlyIGlmIGNvdyZuYnNwO2EmIzM5O3MgcGF0aCBmcm9tIGVudHJ5IHRvIGV4aXQgbXVzdCBjcm9zcyBjb3cmbmJzcDtiJiMzOTtzIHBhdGggZnJvbSBlbnRyeSB0byBleGl0LiBQbGVhc2UgaGVscCBGYXJtZXIgSm9obiBjb3VudCB0aGUgdG90YWwgbnVtYmVyIG9mIGNyb3NzaW5nIHBhaXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOJm5ic3A7KDEgJmxlOyBOICZsZTsgNTAsMDAwKSwgYW5kIHRoZSBuZXh0Jm5ic3A7Mk4gbGluZXMgZGVzY3JpYmUgdGhlIGNvdyBJRHMgZm9yIHRoZSBzZXF1ZW5jZSBvZiBlbnRyeSBhbmQgZXhpdCBwb2ludHMgYXJvdW5kIHRoZSBmaWVsZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2UgcHJpbnQgdGhlIHRvdGFsIG51bWJlciBvZiBjcm9zc2luZyBwYWlycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=