페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8462
서브태스크

삽입정렬 횟수 세기 2 1s 1024MB

문제

임의의 서로 같지 않은 수로 이루어진 수열 A를 삽입정렬을 하고자 한다.

만약 배열 A에 20, 40, 30, 10 이 들어갈 경우 다음과 같이 삽입정렬이 이루어진다.

  1. i = 1 일 때 20, 40, 30, 10. 이동수 : 0

  2. i = 2 일 때 20, 40, 30, 10. 이동수 : 0

  3. i = 3 일 때 20, 30, 40, 10. 이동수 : 1 (40이 움직이고 30이 들어감)

  4. i = 4 일 때 10, 20, 30, 40. 이동수 : 3 (20, 30, 40 이 움직이고 10이 들어감)

총 4번의 밀어내기를 통하여 삽입정렬이 완료된다.

임의의 수열 A가 주어질 경우, 수열의 숫자가 얼마나 이동하는지 출력하는 프로그램을 작성하시오.


입력

처음 줄에는 수열의 개수 N (1≤N≤300,000)이 입력된다.

다음 줄에는 N개의 -10^9 이상 10^9 이하의 정수들 A_1, A_2, \cdots, A_N이 입력된다. 이 수들은 서로 다르다고 가정한다.


출력

입력된 수열에 대한 전체 이동 횟수를 출력하시오.


부분문제

번호 점수 조건
#110점

N \le 300

#220점

|A_i| < 20 (1 \le i \le N)

#330점

0< A_i \le 100,000 (1 \le i \le N)

#440점

추가 제약 조건 없음


예제 #1

4
20 40 30 10
4

예제 #2

3
-1 1 0
1

출처

klee

로그인해야 코드를 작성할 수 있어요.