서로 대응되는 수 a,b가 n/2개 존재함.


각 a,b 페어에 대해

a,b중에 최솟값들만 vector 1에 저장

a,b중에 최댓값들만 최댓값 + k해서 vector 2에 저장

a+b값이 40만까지밖에 안되니 배열하나 잡아서 arr[a+b]++ 해줌

두 vector 모두 정렬함


2부터 40만까지의 합 후보 x에 대해 x마다 최소변환횟수를 lower_bound로 logn만에 구할 수 있음


for(int x = 2; x<=2*k; x++){

n/2페어 전부 1번씩 변환해야 한다고 생각하고 변환횟수 n/2로 잡음

arr[x]만큼 변환 안해도 되는쌍이라 개수만큼 빼줌

최댓값 배열 vector 2에 있는 값들 중 x보다 작은애들은 한 번만에 변환 못하므로 개수구해서 더함

최솟값 배열 vector 1에 있는 값들 중 x와 같거나 x보다 큰 애들 역시 한 번에 변환 못하므로 개수구해서 더함

최소변환 횟수를 갱신함

}


for문이 끝나고 최소변환 횟수 출력한다

o(max(n,k)logn)