시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 156 58 38 44.186%

문제

정렬 알고리즘의 상한(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를 만족하는 세 원소)의 개수를 출력한다.

예제 입력

4
3 3 2 1

예제 출력

2

예제 입력 2

3
1 2 3

예제 출력 2

0

힌트