Submit

Status

Ranklist

Back to Problems List

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

64.7% (11/17)

Description

在這個夏天，很多人都要各奔東西，就像在世界上 70 多億的人裡面與你相遇的機率是那麼的微乎其微，卻又那麼的真實。

小明快要畢業了，他在學校學到了一些能力，他的同學們也學到了一些能力，因為每個人都只是一個人，如果三個人就可以勝過一個諸葛亮。

現在小明班上有 $N$ 個同學，現在老師想要訓練同學合作，三人一組做分組報告。

你是這堂課的老師，要幫他們分組，但是同一組裡面能力最高的那個人的能力值必須小於另外兩個人的能力值和，請問你最多可以分幾組。

（可以有同學不被分到組別，他們就可以爽爽過這堂課）

Input Format

輸入共兩行，
第一行有 $1$ 個整數 $M$ ($1 \leq M \leq 3 \cdot 10^ 5$)，$M$ 代表有幾種不同的能力值。

第二行有 $M$ 個整數 ($1 \leq a_1, a_2 ...a_M \leq 5 \cdot 10^ 5$)，代表能力值為 $2^ {i}$ 的學生有 $a_i$ 個。

Note:
$\sum\limits^ M _{i=1} a_i = N$，班上有 $N$ 個同學。

因為有些人很用功，有些人很混，所以能力值需要使用 $2$ 的對數才能夠好好的表達差異。 QQ

Output Format

輸出共一行，其中包括一個整數，代表組的數量。

Sample Input 1

5
1 2 2 2 2

Sample Output 1

Sample Input 2

3
1 1 1

Sample Output 2

Sample Input 3

3
3 3 3

Sample Output 3

Sample Input 4

3
1 2 2

Sample Output 4

Sample Input 5

10
1 1 1 1 1 1 1 1 8 8

Sample Output 5

Hints

範例一
班上有 $9$ 個人，能力分別為
$2, 4, 4, 8, 8, 16, 16, 32, 32$

老師可以分成 $3$ 組

範例四
班上有 $5$ 人，能力分別為
$2, 4, 4, 8, 8$

老師只能夠分成一組
如：
$(2, 8, 8)$
其他的同學就爽爽過。

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0~4	範例測試資料	10
2	5~17	$1 \leq a_1, a_2 ...a_M \leq 5 \cdot 10^ 5$	90

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1
1	1000	65536	65536	1
2	1000	65536	65536	1
3	1000	65536	65536	1
4	1000	65536	65536	1
5	1000	65536	65536	2
6	1000	65536	65536	2
7	1000	65536	65536	2
8	1000	65536	65536	2
9	1000	65536	65536	2
10	1000	65536	65536	2
11	1000	65536	65536	2
12	1000	65536	65536	2
13	1000	65536	65536	2
14	1000	65536	65536	2
15	1000	65536	65536	2
16	1000	65536	65536	2
17	1000	65536	65536	2