Алиса — лидер Государственной рефакторинговой партии, и она близка к тому, чтобы стать Премьер-министром.
Только что прошли выборы. Всего было \(n\) партий, последовательно пронумерованных от \(1\) до \(n\). \(i\)-я партия получила \(a_i\) мест в парламенте.
Партия Алисы имеет номер \(1\). Чтобы стать Премьер-министром, ей нужно создать коалицию, которая состоит из ее партии и, возможно, других партий. Есть два ограничения на создание коалиции:
- Коалиция должна иметь большинство в парламенте, другими словами, суммарное количество мест всех партий коалиции должно быть строго больше половины мест в парламенте. Например, если в парламенте \(200\) (или \(201\)) мест, то большинство — это \(101\) и больше мест.
- Партия Алисы должна иметь хотя бы в \(2\) раза больше мест в парламенте, чем любая другая партия в коалиции. Например, чтобы взять в коалицию партию с \(50\) местами, у партии Алисы должно быть как минимум \(100\) мест.
Например, если \(n=4\) и \(a=[51, 25, 99, 25]\) (обратите внимание, что партия Алисы получила \(51\) место), то следующий набор \([a_1=51, a_2=25, a_4=25]\) может являться коалицией, так как удовлетворяет обоим условиям, а следующие наборы — нет:
- \([a_2=25, a_3=99, a_4=25]\) — так как не содержит партию Алисы;
- \([a_1=51, a_2=25]\) — так как коалиция должна иметь строгое большинство мест;
- \([a_1=51, a_2=25, a_3=99]\) — так как партия Алисы должна иметь хотя бы в \(2\) раза больше мест в парламенте, чем любая другая партия в коалиции.
Алиса может не минимизировать количество партий в коалиции. Она может пригласить сколько угодно партий, если оба условия будут выполнены. С другой стороны, если партия Алисы имеет достаточное количество мест в парламенте для выполнения первого условия, она может и не приглашать другие партии.
Обратите внимание, что Алиса может либо взять всю партию в коалицию, либо никого из той партии. Нельзя взять только несколько (не всех) депутатов (мест) в другой партии. Другими словами, если она берет партию в коалицию, то она берет всех ее депутатов.
Найдите любую подходящую коалицию.
Выходные данные
Если невозможно создать такую коалицию, то выведите \(0\).
В противном случае, пусть \(k\) (\(1 \leq k \leq n\)) — количество партий в коалиции (Алиса может не минимизировать количество партий в коалиции), а \(c_1, c_2, \dots, c_k\) (\(1 \leq c_i \leq n\)) — номера этих партий. В первой строке выведите \(k\), а во второй \(c_1, c_2, \dots, c_k\).
Вы можете выводить партии в любом порядке. Партия Алисы (номер \(1\)) должна быть в этом списке. Если существует несколько решений, выведите любое из них.
Примечание
В первом примере Алиса пригласила вторую партию. Обратите внимание, она также могла пригласить как третью партию, так и обе эти партии. Но она не смогла бы стать Премьер-министром, не приглашая ни одну партию, потому что \(100\) мест мало для того, чтобы гарантировать большинство в парламенте, где \(200\) мест.
Во втором примере невозможно создать коалицию, так как любая партия слишком большая для того, чтобы пригласить ее в коалицию.
В третьем примере одной лишь партии Алисы достаточно для коалиции.
Четвертый пример объяснен в условии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
100 50 50
|
2
1 2
|
|
2
|
3
80 60 60
|
0
|
|
3
|
2
6 5
|
1
1
|
|
4
|
4
51 25 99 25
|
3
1 2 4
|