#944. 集中的奶牛

集中的奶牛

样例下载

题目描述

Farmer John 的 NN 头奶牛,总是会迷路走到农场上遥远的地方去!他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴,奶牛可以占据数轴上的任意整数位置。这 NN 头奶牛现在正位于不同的整数位置,Farmer John 想要移动她们,使得她们占据 NN 个相邻的位置(例如,位置 66、77、88)。

不幸的是,奶牛们现在很困,Farmer John 要让她们集中精力听从命令移动并不容易。任意时刻,他只能使得一头处在“端点”(在所有奶牛中位置最小或最大)位置的奶牛移动。当他移动奶牛时,他可以命令她走到任意一个未被占用的整数位置,只要在新的位置上她不再是一个端点。可以看到随着时间的推移,这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们全部集中到相邻位置所进行的移动次数的最小和最大可能值。

输入格式

第一行:一个整数 NN

接下来 NN 行,每行一个整数 XiX_i,分别表示一头奶牛的位置。数据保证奶牛的位置两两不同。

输出格式

共两行:

第一行包含 Farmer John 需要将奶牛们聚集起来所需进行的最小移动次数。

第二行包含他将奶牛聚集起来能够进行的最大移动次数。

样例输入

3 
4 
7 
9

样例输出

1
2

数据范围

3≤N≤1053 ≤ N ≤ 10^5, 1≤Xi≤1091 ≤ X_i ≤ 10^9