이상한 정렬 timer 1s memory 1024MB

이제 막 정렬 알고리즘을 배운 지호.

지호가 배운 정렬 알고리즘은 아래와 같다.

< 알고리즘 >

정렬할 배열을 [~A_1, A_2, ..., A_N~] 이라 하면,

for i : 1 부터 N 까지

ㅤㅤfor j : 1 부터 N 까지

ㅤㅤㅤㅤif A_i < A_j 라면:

ㅤㅤㅤㅤㅤㅤ A_i 와 A_j 를 바꾼다. ←------ (1)

언뜻 보면 위 <알고리즘> 은 제대로 정렬을 못 할 것 같지만, 놀랍게도 이 <알고리즘>은 정확한 정렬 알고리즘이다.

지호는 호기심이 발동했다.

"맨 앞 K 개의 원소만 존재할 때, (1)번 명령이 몇 번 실행될까?"

예를 들어 N = 5, 배열이 [ 2 4 1 2 3 ] 이라 하자.

K = 2 라면 맨 앞 2개인 [ 2 4 ] 배열만 정렬하는 것이고, 이 때 (1)번 명령은 2번 실행된다.

K = 3 이라면 맨 앞 3개인 [ 2 4 1 ] 배열만 정렬하는 것이고, 이 때 (1)번 명령은 4번 실행된다.

K = 5 라면, 전체 배열 [ 2 4 1 2 3 ] 을 정렬하는 것이고, (1)번 명령은 6번 실행된다.

지호는 모든 K = 1, 2, ... N 에 대해 이 질문에 대한 답을 구하고 싶다.

위 예시에서는 답이 0, 2, 4, 5, 6 이 된다.

지호를 도와 각 K 에 대한 답을 구해주자.