给定一个整数N。我们需要找出排列和PermutationSum，其中整数N的排列和被定义为从1到N的所有数字排列中相邻元素之差的最大和。
例如，当N=3时，答案是3。
解释：对于N=3，可能的排列方式为：
{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}
给定排列{1,2,3}，PermutationSum的值为2，即abs(1-2)+abs(2-3)=2。
给定排列{1,3,2}，PermutationSum的值为3。
给定排列{2,1,3}，PermutationSum的值为3。
给定排列{2,3,1}，PermutationSum的值为3。
给定排列{3,1,2}，PermutationSum的值为3。
给定排列{3,2,1}，PermutationSum的值为2。
因此，所有排列中PermutationSum的最大值为3。
我们需要找到N个元素的排列中的PermutationSum最大值，其中N最大为100000。
我有一个N!的解决方案。但是对于较大的N，它无法工作。