P5849 [IOI 2015] boxes

The opening ceremony of IOI 2015 is in its final part. According to the plan, during the ceremony, each delegation should receive a box containing souvenirs provided by the organizers. However, all volunteers were attracted by the wonderful ceremony and completely forgot about distributing the souvenirs, except Aman. Aman is an enthusiastic volunteer, and to make IOI as successful as possible, he wants to distribute all souvenirs in the shortest time. The ceremony venue is a circular ring divided into $L$ equal areas. These areas are numbered from $0$ to $L-1$. That is, for $0\le i\le L-2$, area $i$ is adjacent to area $i+1$, and area $L-1$ is adjacent to area $0$. There are $N$ delegations in total, each sitting in one of these areas. Each area may contain any number of delegations, and it may also be empty. There are $N$ identical souvenirs. At the beginning, Aman and all souvenirs are in area $0$. Aman should give one souvenir to each delegation, and after distributing the last souvenir, he must return to area $0$. Note that some delegations may be in area $0$. At any moment, Aman can carry at most $K$ souvenirs. Aman must take these souvenirs from area $0$, and taking souvenirs takes no time. Once a souvenir is taken from area $0$, Aman can only give it to some delegation or carry it with him. Whenever Aman arrives at an area while carrying one or more souvenirs, and that area has at least one delegation that has not yet received a souvenir, Aman can give one of the souvenirs he is carrying to that delegation. This distribution is also instantaneous. The time he spends is only on moving between areas. No matter how many souvenirs he carries, Aman needs $1$ second to move from one area to an adjacent area (he can move clockwise or counterclockwise). Your task is to compute the minimum time (in seconds) Aman needs to distribute all souvenirs and return to his initial area.

- Line $1$ contains three integers $N$, $K$, $L$, representing the number of delegations, the maximum number of souvenirs Aman can carry each time, and the number of areas in the venue, respectively. - Line $2$ contains $N$ integers $p[0],\cdots,p[N−1]$, where $p[i]$ ($0\le i\le N-1$) denotes the area index where the $i$-th delegation is located. The elements of $p$ are sorted in non-decreasing order.

One line containing the minimum time (in seconds) Aman needs.

For $100\%$ of the testdata, $1\le N\le 10^7$, $1\le K\le N$, $1\le L\le 10^9$. Translated by ChatGPT 5