시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 459 182 128 39.385%

문제

정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i < j)를 선택하고, 그 위치를 서로 바꿔준다. 이렇게 올바른 순서가 아닌 것을 도치(inversion)라고 하며, 도치의 개수는 최대 n(n-1)/2개이다. 

현주는 사회에 대한 불만이 많은 아이이다. 그는 항상 정렬을 할 때, 두 원소를 선택하는 것에도 큰 불만을 가지고 있다. 현주는 ai > aj > ak와 i < j < k를 만족하는 세 원소를 선택한 뒤, ak, aj, ai로 순서를 바꾸려고 한다.

현주는 자신이 만든 정렬 알고리즘을 불만 정렬 알고리즘이라고 이름을 붙였다. 이제 이 알고리즘의 상한을 구하려고 한다. 현주가 선택할 수 있는 세 원소의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이가 주어진다. (1 ≤ n ≤ 105)

다음 줄에는 수열의 원소가 공백으로 구분되어 주어진다. 각 원소는 1보다 크거나 같고, n보다 작거나 같은 정수이다.

출력

첫째 줄에 도치된 세 원소 (ai > aj > ak와 i < j < k를 만족하는 세 원소)의 개수를 출력한다.

예제 입력 1

4
3 3 2 1

예제 출력 1

2

예제 입력 2

3
1 2 3

예제 출력 2

0
W3sicHJvYmxlbV9pZCI6IjUwMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODhcdWI5Y2MgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWI4MmMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzU4IFx1YzBjMVx1ZDU1Yyh1cHBlciBib3VuZClcdWM3NDAgbjxzdXA+MjxcL3N1cD5cdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDAgXHVjMjdkXHVhYzhjIFx1Yzk5ZFx1YmE4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MmNcdWJjMTRcdWI5NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1YzZkMFx1YzE4YyhhPHN1Yj5pPFwvc3ViPiAmZ3Q7IGE8c3ViPmo8XC9zdWI+LCBpICZsdDsgailcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWJjMTRcdWFmZDRcdWM5MDBcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM2MmNcdWJjMTRcdWI5NzggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWFjODNcdWM3NDQgXHViM2M0XHVjZTU4KGludmVyc2lvbilcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTcwLCBcdWIzYzRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBuKG4tMSlcLzJcdWFjMWNcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzhmY1x1YjI5NCBcdWMwYWNcdWQ2OGNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YmQ4OFx1YjljY1x1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVjNTQ0XHVjNzc0XHVjNzc0XHViMmU0LiBcdWFkZjhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWQ1NjAgXHViNTRjLCBcdWI0NTAgXHVjNmQwXHVjMThjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM1ZDBcdWIzYzQgXHVkMDcwIFx1YmQ4OFx1YjljY1x1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM4ZmNcdWIyOTQgYTxzdWI+aTxcL3N1Yj4gJmd0OyBhPHN1Yj5qPFwvc3ViPiAmZ3Q7IGE8c3ViPms8XC9zdWI+XHVjNjQwIGkgJmx0OyBqICZsdDsga1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMTM4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHViNGE0LCBhPHN1Yj5rPFwvc3ViPiwgYTxzdWI+ajxcL3N1Yj4sIGE8c3ViPmk8XC9zdWI+XHViODVjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM4ZmNcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YjljY1x1YjRlMCBcdWM4MTVcdWI4MmMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YmQ4OFx1YjljYyBcdWM4MTVcdWI4MmMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0XHViNzdjXHVhY2UwIFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWJkOTlcdWM2MDBcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWM3NzQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzU4IFx1YzBjMVx1ZDU1Y1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2MDRcdWM4ZmNcdWFjMDAgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTM4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzZkMFx1YzE4Y1x1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIG5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWNlNThcdWI0MWMgXHVjMTM4IFx1YzZkMFx1YzE4YyAoYTxzdWI+aTxcL3N1Yj4mbmJzcDsmZ3Q7IGE8c3ViPmo8XC9zdWI+Jm5ic3A7Jmd0OyBhPHN1Yj5rPFwvc3ViPlx1YzY0MCBpICZsdDsgaiAmbHQ7IGtcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzEzOCBcdWM2ZDBcdWMxOGMpXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTAxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1lZ2EgSW52ZXJzaW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG48c3VwPjI8XC9zdXA+IHVwcGVyIGJvdW5kIGZvciBhbnkgc29ydGluZyBhbGdvcml0aG0gaXMgZWFzeSB0byBvYnRhaW46IGp1c3QgdGFrZSB0d28gZWxlbWVudHMgdGhhdCBhcmUgbWlzcGxhY2VkIHdpdGggcmVzcGVjdCB0byBlYWNoIG90aGVyIGFuZCBzd2FwIHRoZW0uIENvbnJhZCBjb25jZWl2ZWQgYW4gYWxnb3JpdGhtIHRoYXQgcHJvY2VlZHMgYnkgdGFraW5nIG5vdCB0d28sIGJ1dCB0aHJlZSBtaXNwbGFjZWQgZWxlbWVudHMuIFRoYXQgaXMsIHRha2UgdGhyZWUgZWxlbWVudHMgJm5ic3A7YTxzdWI+aTxcL3N1Yj4mbmJzcDsmZ3Q7IGE8c3ViPmo8XC9zdWI+Jm5ic3A7Jmd0OyBhPHN1Yj5rPFwvc3ViPiB3aXRoIGkgJmx0OyBqICZsdDsgayBhbmQgcGxhY2UgdGhlbSBpbiBvcmRlciAmbmJzcDthPHN1Yj5rPFwvc3ViPiwgYTxzdWI+ajxcL3N1Yj4sIGE8c3ViPmk8XC9zdWI+LiBOb3cgaWYgZm9yIHRoZSBvcmlnaW5hbCBhbGdvcml0aG0gdGhlIHN0ZXBzIGFyZSBib3VuZGVkIGJ5IHRoZSBtYXhpbXVtIG51bWJlciBvZiBpbnZlcnNpb25zIG4obi0xKVwvMiwgQ29ucmFkIGlzIGF0IGhpcyB3aXRzJiMzOTsgZW5kIGFzIHRvIHRoZSB1cHBlciBib3VuZCBmb3Igc3VjaCB0cmlwbGVzIGluIGEgZ2l2ZW4gc2VxdWVuY2UuIEhlIGFza3MgeW91IHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvdW50cyB0aGUgbnVtYmVyIG9mIHN1Y2ggdHJpcGxlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSwgMSAmbHQ7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4uPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgc2VxdWVuY2UgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4gLCBhPHN1Yj5uPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+WW91IGNhbiBhc3N1bWUgdGhhdCBhbGwgYTxzdWI+aTxcL3N1Yj4gJmlzaW47IFsxLCBuXS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBpbnZlcnRlZCB0cmlwbGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==