You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小杜 和 小徐 轮流取石子。

每次可以选择一个 $i\in[1,n],a_i\ge l$，取 $l\sim \min(a_i,r)$ 的石子。

小杜 希望它们两个取石子的差最大，小徐 希望它们两个取石子的差最小。

小杜是先手，小徐是后手。

请你输出两个人在采用最优情况下，取得石子数分别是多少。

输入格式

• 第一行 $3$ 个正整数 $n,l,r$。
• 第二行 $n$ 个整数，表示 $a$ 数列。

输出格式

一行 $2$ 个正整数，表示 小杜 和 小徐 取的石子数。

3 2 3
3 2 1

3 2

样例解释 #1

一种最优策略如下(括号内第一个数为 $i$，第二个数为取得石子数)：

• 小杜：$\{1,3\}$
• 小徐：$\{2,2\}$

5 1 3
1 2 3 4 5

9 6

样例解释 #2

一种最优策略如下(括号内第一个数为 $i$，第二个数为取得石子数)：

• 小杜：$\{3,3\},\{5,3\},\{5,2\},\{1,1\}$
• 小徐：$\{4,3\},\{2,2\},\{4,1\}$

10 1 5
2 2 3 3 5 5 5 5 8 8

23 23

30 1 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

235 230

数据范围

对于 $5\%$ 的数据，$1\le n\le 1，1\le a_i,l,r\le 5$。

对于 $10\%$ 的数据，$1\le n\le 2，1\le a_i,l,r\le 5$。

对于 $30\%$ 的数据，$1\le n\le 5，1\le a_i,l,r\le 5$。

对于 $50\%$ 的数据，$1\le n\le 10^3,1\le a_i,l,r\le 10^3$。

对于另外 $10\%$ 的数据，$l=r$。

对于 $100\%$ 的数据，$1\le n\le 10^6,1\le a_i,l,r\le 10^9$。

保证 $l\le r$。