시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 280 139 109 53.695%

문제

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

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

이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 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+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHViNDUwIFx1YzE4Y1x1YjI5NCBcdWM1YjRcdWI1YTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM3N1x1YjRlMCBcdWFkZjggXHVhY2JkXHViODVjXHVhYzAwIFx1YzViNFx1YjUxOFx1YWMwMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWM1N2MgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWMxOGNcdWFjMDAgXHVjZDFkIFx1YmE4NyBcdWMzMGRcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiAoMSAmbGU7IE4gJmxlOyA1MCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIDJOXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWUzOCBcdWM3MDRcdWM3NTggXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwNCBcdWMxOGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjYmRcdWI4NWNcdWFjMDAgXHViYjM0XHVjODcwXHVhYzc0IFx1YjljY1x1YjA5OFx1YjI5NCBcdWMxOGNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNDQ2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCBJSUkgKEdvbGQpIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbGF5b3V0IG9mIEZhcm1lciBKb2huJiMzOTtzIGZhcm0gaXMgcXVpdGUgcGVjdWxpYXIsIHdpdGggYSBsYXJnZSBjaXJjdWxhciByb2FkIHJ1bm5pbmcgYXJvdW5kIHRoZSBwZXJpbWV0ZXIgb2YgdGhlIG1haW4gZmllbGQgb24gd2hpY2ggaGlzIGNvd3MgZ3JhemUgZHVyaW5nIHRoZSBkYXkuIEV2ZXJ5IG1vcm5pbmcsIHRoZSBjb3dzIGNyb3NzIHRoaXMgcm9hZCBvbiB0aGVpciB3YXkgdG93YXJkcyB0aGUgZmllbGQsIGFuZCBldmVyeSBldmVuaW5nIHRoZXkgYWxsIGNyb3NzIGFnYWluIGFzIHRoZXkgbGVhdmUgdGhlIGZpZWxkIGFuZCByZXR1cm4gdG8gdGhlIGJhcm4uPFwvcD5cclxuXHJcbjxwPkFzIHdlIGtub3csIGNvd3MgYXJlIGNyZWF0dXJlcyBvZiBoYWJpdCwgYW5kIHRoZXkgZWFjaCBjcm9zcyB0aGUgcm9hZCB0aGUgc2FtZSB3YXkgZXZlcnkgZGF5LiBFYWNoIGNvdyBjcm9zc2VzIGludG8gdGhlIGZpZWxkIGF0IGEgZGlmZmVyZW50IHBvaW50IGZyb20gd2hlcmUgc2hlIGNyb3NzZXMgb3V0IG9mIHRoZSBmaWVsZCwgYW5kIGFsbCBvZiB0aGVzZSBjcm9zc2luZyBwb2ludHMgYXJlIGRpc3RpbmN0IGZyb20gZWFjaC1vdGhlci4gRmFybWVyIEpvaG4gb3ducyZuYnNwO05OJm5ic3A7Y293cywgY29udmVuaWVudGx5IGlkZW50aWZpZWQgd2l0aCB0aGUgaW50ZWdlciBJRHMmbmJzcDsxJmhlbGxpcDtOLCBzbyB0aGVyZSBhcmUgcHJlY2lzZWx5Jm5ic3A7Mk4yTiZuYnNwO2Nyb3NzaW5nIHBvaW50cyBhcm91bmQgdGhlIHJvYWQuIEZhcm1lciBKb2huIHJlY29yZHMgdGhlc2UgY3Jvc3NpbmcgcG9pbnRzIGNvbmNpc2VseSBieSBzY2FubmluZyBhcm91bmQgdGhlIGNpcmNsZSBjbG9ja3dpc2UsIHdyaXRpbmcgZG93biB0aGUgSUQgb2YgdGhlIGNvdyBmb3IgZWFjaCBjcm9zc2luZyBwb2ludCwgdWx0aW1hdGVseSBmb3JtaW5nIGEgc2VxdWVuY2Ugd2l0aCZuYnNwOzJOIG51bWJlcnMgaW4gd2hpY2ggZWFjaCBudW1iZXIgYXBwZWFycyBleGFjdGx5IHR3aWNlLiBIZSBkb2VzIG5vdCByZWNvcmQgd2hpY2ggY3Jvc3NpbmcgcG9pbnRzIGFyZSBlbnRyeSBwb2ludHMgYW5kIHdoaWNoIGFyZSBleGl0IHBvaW50cy48XC9wPlxyXG5cclxuPHA+TG9va2luZyBhdCBoaXMgbWFwIG9mIGNyb3NzaW5nIHBvaW50cywgRmFybWVyIEpvaG4gaXMgY3VyaW91cyBob3cgbWFueSB0aW1lcyB2YXJpb3VzIHBhaXJzIG9mIGNvd3MgbWlnaHQgY3Jvc3MgcGF0aHMgZHVyaW5nIHRoZSBkYXkuIEhlIGNhbGxzIGEgcGFpciBvZiBjb3dzJm5ic3A7KGEsYikmbmJzcDthICZxdW90O2Nyb3NzaW5nJnF1b3Q7IHBhaXIgaWYgY293Jm5ic3A7YSYjMzk7cyBwYXRoIGZyb20gZW50cnkgdG8gZXhpdCBtdXN0IGNyb3NzIGNvdyZuYnNwO2ImIzM5O3MgcGF0aCBmcm9tIGVudHJ5IHRvIGV4aXQuIFBsZWFzZSBoZWxwIEZhcm1lciBKb2huIGNvdW50IHRoZSB0b3RhbCBudW1iZXIgb2YgY3Jvc3NpbmcgcGFpcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyZuYnNwO04mbmJzcDsoMSAmbGU7IE4gJmxlOyA1MCwwMDApLCBhbmQgdGhlIG5leHQmbmJzcDsyTiBsaW5lcyBkZXNjcmliZSB0aGUgY293IElEcyBmb3IgdGhlIHNlcXVlbmNlIG9mIGVudHJ5IGFuZCBleGl0IHBvaW50cyBhcm91bmQgdGhlIGZpZWxkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBwcmludCB0aGUgdG90YWwgbnVtYmVyIG9mIGNyb3NzaW5nIHBhaXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d