← 返回题目列表

Codeforces · 1121/B

B. 迈克和孩子们

中文机器翻译题面 查看原题

迈克决定在一所小学教孩子们编程。他知道让那个年龄段的孩子对编程产生兴趣并不是一件容易的事。这就是为什么他决定给每个孩子两块糖果。

迈克有 $$$n$$$ 糖果,尺寸为 $$$a_1、a_2、\ldots、a_n$$$。他所有的糖果都有不同的尺寸。也就是说,不存在这样的对 $$$(i, j)$$$ ($$$1 \leq i, j \leq n$$$) 使得 $$$i \ne j$$$ 和 $$$a_i = a_j$$$。

由于 Mike 教书多年,他知道如果他给一个孩子两块尺寸为 $$$a_i$$$ 和 $$$a_j$$$ 的糖果,给另一个孩子 $$$a_k$$$ 和 $$$a_p$$$,其中 $$$(a_i + a_j) \neq (a_k + a_p)$$$,那么尺寸总和较小的孩子将是心烦意乱。也就是说,如果有两个孩子拥有不同数量的糖果,那么其中一个就会不高兴。显然,迈克不希望有人感到不安。

迈克想邀请孩子们每人两块糖果。显然,他不能给两个或更多的孩子一颗糖。他的目标是邀请尽可能多的孩子。

由于迈克正忙着准备他在小学的第一堂课,他要求你找出他可以邀请的最大数量的孩子,给他们每人两块糖果,这样就不会有人不高兴。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 1\,000$$$) — 迈克拥有的糖果数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — 糖果的大小。保证所有整数都是不同的。

输出

打印一个整数——迈克可以邀请的最大数量的孩子,每人给他们两块糖果,这样就不会有人不高兴。

示例

输入 #1

8
1 8 3 11 4 9 2 7

输出 #1

3

输入 #2

7
3 1 7 11 9 2 12

输出 #2

2

注意

在第一个示例中,Mike 可以将 $$$9+2=11$$$ 给一个孩子,$$$8+3=11$$$ 给另一个孩子,$$$7+4=11$$$ 给第三个孩子。因此,迈克可以邀请三个孩子。请注意,这不是唯一的解决方案。

在第二个示例中,Mike 可以将 $$$3+9=12$$$ 给一个孩子,将 $$$1+11$$$ 给另一个孩子。因此,迈克可以邀请两个孩子。请注意,这不是唯一的解决方案。