新的家乡

Luogu

IDLGP8587

Time1000ms

Memory128MB

DifficultyP3

O2优化

你作为第一批科研人员，提前来到了 $\beta$ 星建造基地。 $\beta$ 星盛产锰钛矿石。基地需要一些**高度相同**的柱子，而每根柱子都需要由**恰好**两根锰钛矿石顺次连接组成。例如，若你有两根高度分别为 $h_x,h_y$ 的锰钛矿石，那么你可以用两者合成为一根高度为 $h_x+h_y$ 的柱子。每根锰钛矿石**显然至多被使用一次**。现在你来到了 $\beta$ 星的锰钛矿场，摆在你面前的是 $n$ 根高度分别为 $h_i$ 的锰钛矿石。经过严密思考后你发现，房屋的牢固程度应该取决于柱子的数目，而不是柱子的高度。所以你想知道，使用面前这 $n$ 根矿石最多可以建造出多少根高度相同的柱子？但小花觉得这个问题太 easy 了，于是 ta 选择多问你一嘴：假设柱子高度均为 $h$，基地最多可以建出 $\mathrm{res}$ 根柱子，那么在柱子数目同为 $\mathrm{res}$ 时 $h$ 可以有几种不同的取值？ ## Input 输入共两行。第一行共一个正整数 $n$，表示锰钛矿石的数量。第二行共 $n$ 个正整数 $h_i$，含义见题目描述。 ## Output 输出共一行两个整数 $\mathrm{res}$ 和 $\mathrm{ans}$，分别表示最多的柱子数目以及最优答案下有多少种不同的高度方案。 [samples] ## Background 2102 年，太阳系的生态终于不再支持人类的生存。人类打算沿着之前建好的星际长途路线去往金牛座蟹状星云中的某行星 $\beta$ 谋求发展。 ## Note 额外样例见附加文件 `ex.in/out`。对于 $20\%$ 的数据，$1\leq n\leq 100$。对于 $40\%$ 的数据，$1\leq n \leq 10^3$。对于 $70\%$ 的数据，$1\leq n\leq 10^5$。对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq h_i \leq 3\times 10^3$。

Samples

Input #1

4
4 7 6 5

Output #1

2 1

Input #2

6
1 1000 100 1500 10 1800

Output #2

1 15

API Response (JSON)

{
  "problem": {
    "name": "新的家乡",
    "description": {
      "content": "你作为第一批科研人员，提前来到了 $\\beta$ 星建造基地。 $\\beta$ 星盛产锰钛矿石。基地需要一些**高度相同**的柱子，而每根柱子都需要由**恰好**两根锰钛矿石顺次连接组成。例如，若你有两根高度分别为 $h_x,h_y$ 的锰钛矿石，那么你可以用两者合成为一根高度为 $h_x+h_y$ 的柱子。每根锰钛矿石**显然至多被使用一次**。 现在你来到了 $\\beta$ 星的锰钛矿场，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8587"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你作为第一批科研人员，提前来到了 $\\beta$ 星建造基地。\n\n$\\beta$ 星盛产锰钛矿石。基地需要一些**高度相同**的柱子，而每根柱子都需要由**恰好**两根锰钛矿石顺次连接组成。例如，若你有两根高度分别为 $h_x,h_y$ 的锰钛矿石，那么你可以用两者合成为一根高度为 $h_x+h_y$ 的柱子。每根锰钛矿石**显然至多被使用一次**。\n\n现在你来到了 $\\beta$ 星的锰钛矿场，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments