Arithmetic progression sum: 1+2+. . . k=( 1+k)k/2
Arithmetic progression sum in the second half: 1+2+. . . (k- 1)=k(k- 1)/2
Together, it is NK-(1+k) k/2-k (k-1)/2.
The latter two items are combined to get the answer.