C. Gorilla and Permutation

Gorilla and Noobish_Monk found three numbers 𝑛, 𝑚, and 𝑘 (𝑚<𝑘). They decided to construct a permutation† of length 𝑛.

For the permutation, Noobish_Monk came up with the following function: 𝑔(𝑖) is the sum of all the numbers in the permutation on a prefix of length 𝑖 that are not greater than 𝑚. Similarly, Gorilla came up with the function 𝑓, where 𝑓(𝑖) is the sum of all the numbers in the permutation on a prefix of length 𝑖 that are not less than 𝑘. A prefix of length 𝑖 is a subarray consisting of the first 𝑖 elements of the original array.

For example, if 𝑛=5, 𝑚=2, 𝑘=5, and the permutation is [5,3,4,1,2], then:

• 𝑓(1)=5, because 5≥5; 𝑔(1)=0, because 5>2;
• 𝑓(2)=5, because 3<5; 𝑔(2)=0, because 3>2;
• 𝑓(3)=5, because 4<5; 𝑔(3)=0, because 4>2;
• 𝑓(4)=5, because 1<5; 𝑔(4)=1, because 1≤2;
• 𝑓(5)=5, because 2<5; 𝑔(5)=1+2=3, because 2≤2.

Help them find a permutation for which the value of (∑𝑖=1𝑛𝑓(𝑖)−∑𝑖=1𝑛𝑔(𝑖)) is maximized.