410259: GYM103994 A Фальшивая стопка

A. Фальшивая стопкаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Перед вами $$$n$$$ стопок монет. Во всех стопках, кроме одной, каждая монета весит ровно $$$x$$$ миллиграмм, а в оставшейся стопке каждая монета весит ровно $$$y$$$ миллиграмм. Далее будем называть эту стопку фальшивой.

Вам нужно определить номер фальшивой стопки.

У вас есть сверхточные весы, на которые можно положить любое количество монет из любых стопок и они покажут их точный суммарный вес. Однако батарея весов быстро садится при использовании, так что вы хотите обойтись минимальным количеством взвешиваний.

Скользо взвешиваний нужно сделать, чтобы гарантированно определить номер фальшивой стопки?

Входные данные

В первой строке ввода дано единственное целое число $$$n$$$ $$$(2 \le n \le 200\,000)$$$ — количество стопок с монетами.

Во второй строке даны два целых числа $$$x$$$ и $$$y$$$ $$$(1 \le x, y \le 10^9, x \neq y)$$$ — веса монет в обычных и фальшивой стопках соответственно.

В третьей строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — количества монет в соответствующих стопках.

Выходные данные

Выведите единственное число — минимальное количество взвешиваний, которое необходимо, чтобы гарантированно определить номер фальшивой стопки.

ПримерыВходные данные

2
1 2
1 1

Выходные данные

1

Входные данные

3
2 1
1 2 1

Выходные данные

1

Входные данные

4
2 3
1 1 3 1

Выходные данные

2

Примечание

В первом тесте на весы можно положить монету из первой стопки. Если показанный вес будет равен 2, то эта стопка фальшивая, иначе вторая стопка фальшивая.

Во втором тесте можно положить на весы одну монету из первой стопки и две монеты из второй стопки. Разберем случаи:

- если весы показывают 6, то все монеты на них настоящие, то есть фальшивая стопка номер 3

- если весы показывают 5, значит монета из первой стопки фальшивая

- если весы показывают 4, значит монеты из второй стопки фальшивые

В третьем примере положим на весы по монете из первых двух стопок. Если число на весах 4, значит среди них нет фальшивой монеты. Иначе - есть.

После одного взвешивания у нас осталось два варианта, какая стопка фальшивая. Положим монету из одной из них на весы и узнаем — какая она.