P4801 [CCO 2015] Hungry Fox

**This problem is translated from [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2015/index.html) Day 1 T1 “[Hungry Fox](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2015/stage%202/day1.pdf)”.** It is dinner time for your pet fox. His dinner contains $N$ cookies, and the temperature of the $i$-th cookie is $T_i$ degrees Celsius. Also, there is a large bowl of water at $W$ degrees Celsius. After taking a sip of water, your fox starts eating. Each time he eats a cookie, the tastiness of this cookie is the absolute value of the difference between the current cookie’s temperature and the temperature of the previous item he ate or drank (including both cookies and water). He may drink water at any time (the water never runs out), and he may eat the cookies in any order. The fox’s final tastiness value is the sum of the tastiness of every cookie he eats. Please find the minimum and maximum possible tastiness values the fox can obtain.

The first line contains two integers $N, W$, representing the number of cookies and the temperature of the water. The next $N$ lines each contain one integer $T_i \ (1 \le i \le N)$, representing the temperature of the $i$-th cookie.

Output two integers: the minimum and the maximum tastiness values the fox can obtain.

To achieve the minimum tastiness value, one possible plan is: the fox drinks water first, then eats the first cookie, then the third cookie, then drinks water, and finally eats the second cookie. In this way, the temperatures he experiences are $20, 18, 18, 20, 25$ degrees Celsius, and the total tastiness is $2 + 0 + 5 = 7$. To achieve the maximum tastiness value, one possible plan is: the fox drinks water first, then eats the cookies in order. The temperatures he experiences are $20, 18, 25, 18$ degrees Celsius, and the total tastiness is $2 + 7 + 7 = 16$. For at least $30\%$ of the testdata, $W = 0$. For $100\%$ of the testdata, $1 \le N \le 100000$, $0 \le W \le 10^9$, $0 \le T_i \le 10^9$. Translated by ChatGPT 5