1919: Мафія
Перегляд у форматі PDFПшеницьк - столиця Рутенської мафії. І саме тут, частіше за все, між бандами виникають конфлікти. Усього в Пшеницьку є ~n~ мафіозних організацій. Нам відомо, що в ~i~-го угрупування - сила ~a_i~.
Під час конфлікту між ~i~-ою та ~j~-ою мафіозною організацією, сильніша поглинає слабшу. Тобто якщо ~a_i >= a_j~, то ~i~-та банда знищує ~j~-ту. При цьому сила ~i~-ої мафії після поглинання змінюється на суму ~a_i + a_j~.
Нам відомо сили всіх ~n~ мафій. Потрібно дізнатись, які з них після ~n-1~ конфлікту можуть встановити абсолютний контроль в Пшеницьку. Іншими словами, які з всіх ~n~ банд можуть поглинути всі інші.
Наприклад, маємо ~n~ = 4 мафій, і такий масив сил a = ~[1, 3, 2, 4]~:
- Очевидно, що мафія під номером ~1~ ніяк не може поглинути інші.
- Мафія ~i=2~ може в будь-якому порядку поглинути угрупування ~1~ і ~3~, після чого сила стане ~a_2 = a_2 + a_1 + a_3 = 1+3+2=6~. Бачимо що ~6 > a_4~, це означає що ми можемо поглинути ~4~-те угрупування і отримати повний контроль над містом.
- Мафія ~i = 3~ може лише поглинути банду під номером ~1~ і отримати силу ~3~.
- Мафія ~i=4~ може поглинути всіх інші в будь-якому порядку. Відповіддю будуть номера ~[2,4]~.
Input
Перший рядок вхідних даних містить число ~n~ ~(1 \leq n \leq 10^5)~ – кількість мафій.
Другий рядок містить ~n~ чисел ~a_i~ ~(1 \leq a_i \leq 10^9)~ – сила ~i~-ої мафії.
Output
У першому рядку виведіть число ~k~ – кількість угрупувань, які можуть отримати повний контроль над Пшеницьком. У другому рядку через пробіл виведіть ~k~ чисел – номери мафій. Номери виводити в порядку зростяння.
Sample Input 1
4
1 3 2 4
Sample Output 1
2
2 4
Коментарі
перевірте будьласка час для пайтона (робив через sort щоб прискорити)
дещо збільшив час для Пайтона
можете будьласка написати вхідні дані в 13 тесті
тут не в 13 тесті проблема. У тебе два вкладені цикли (квадратична складність алгоритму), а при кількості вхідних порядку 10^5 такий алгоритм не вкладеться у визначений час