2189: Максимізувати
Переглянути як PDFВам дається послідовність з ~N~ степенів цілого числа ~k~; позначимо ~i~-й член послідовності ~k^{A_i}~. Ви повинні розділити цю послідовність на дві непорожні суміжні підпослідовності; кожен елемент послідовності повинен бути обов'язково в одній із підпослідовностей. Крім цього, добуток суми елементів лівої підпослідовності і суми елементів правої підпослідовності повинен бути максимально можливим.
Ваша програма має знайти найменшу позицію елемента, який поділить послідовність на дві підпослідовності з описаними вимогами. Шуканий елемент буде відноситися до лівої підпослідовності.
Input
Перший рядок містить одне ціле число ~T~ (~1 \le T \le 10~) - кількість тестів.
Далі ідуть тести у наступному форматі:
Перший рядок кожного тесту містить два цілих числа, розділені пропусками ~N~, ~k~ (~2 \le N \le 10^5~, ~2 \le k \le 10^9~).
Другий рядок тесту містить ~N~ цілих чисел, розділених пропусками ~A_1, A_2,…, A_N~ (~0 \le A_i \le 10^5~).
Output
Для кожного тесту виведіть один рядок, що містить одне ціле число - розмір лівої підпослідовності. Якщо є декілька можливих відповідей, виведіть найменшу.
Sample Input 1
1
5 2
1 1 3 3 5
Sample Output 1
4
Notes
Наша послідовність [~2^1,2^1,2^3,2^3,2^5~] = [2,2,8,8,32]. Максимальний добуток ~20 \cdot 32 = 640~. Оптимально послідовність розбивається на [2,2,8,8] і [32].
Коментарі
чи вистачає часу для python?
для розвʼязків на Пайтоні не надавалася компенсація на ІІ етаапі і не планується надання такої компенсації на ІІІ етапі
окей. Чи є/буде рішення задачі на python?
ні
почув