纸带折叠

题目描述

一条纸带可以看作一条数轴。纸带上有 $n$ 个标记点，第 $i$ 个标记点的坐标为 $x_i$，所有坐标均互不相同的整数。

你可以选择一个实数 $c$，沿坐标为 $c$、垂直于纸带的直线将纸带的一侧翻到另一侧。折叠后，原来位于折线两侧的两个标记点可能重合。

若两个不同的标记点折叠后位于同一位置，则称它们形成一对重合点。每个标记点至多属于一对重合点。

请你求出：

1. 一次对折最多能形成多少对重合点；
2. 有多少条不同的折线能够达到这个最大值。

两条折线的位置 $c$ 不同，就视为不同的折线。折线可以经过标记点，也可以位于两个整数坐标之间。

输入格式

从文件 fold.in 中读入数据。

第一行一个整数 $n$。 第二行 $n$ 个互不相同的整数 $x_1,x_2,\dots,x_n$，表示所有标记点的坐标。

输出格式

输出到文件 fold.out 中。

输出两个整数 \(M,K\)：

• $M$ 表示最多能形成的重合点对数；
• $K$ 表示能够形成恰好 $M$ 对重合点的不同折线条数。

样例输入

5
0 1 2 3 4

样例输出

2 3

样例解释

当 $2c$ 分别为 \(3,4,5\) 时，都能形成 $2$ 对重合点，因此最优折线共有 $3$ 条。

数据规模与约定

对于所有数据：

• $2 \le n \le 3000$；
• $|x_i| \le 10^{12}$；
• 所有 $x_i$ 互不相同。

本题采用子任务测试。只有通过一个子任务中的所有测试点，才能获得该子任务的全部分数。