Фермер Джон дав Бесі масив \(a\) довжини \(N\) (\(2\le N\le 500, -10^{15}\le a_i\le 10^{15}\)) і всі \(\frac{N(N+1)}{2}\) суми безперервних підмасивів різні. Для кожного індексу \(i\in [1,N]\), допоможіть Бесі обчислити мінімальну кількість дій, щоб змінити \(a_i\) так, щоб з'явилися два різних безперервних підмасивів \(a\) з рівними сумами.

Формат вхідних даних

Перший рядок містить \(N\).

Наступний рядок містить \(a_1,\dots, a_N\) (елементи масиву \(a\), по порядку).

Формат вихідних даних

Один рядок для кожного індексу \(i\in [1,N]\).

Приклад вхідних даних

2
2 -3

Приклад вихідних даних

2
3

Збільшивши \(a_1\) або зменшивши \(a_3\) на \(1\) отримаємо \(a_1=a_3\). Збільшивши \(a_2\) на \(6\) отримаємо \(a_1=a_1+a_2+a_3\).

ОЦІНЮВАННЯ:

• Тест 3: \(N\le 40\)
• Тест 4: \(N \le 80\)
• Тести 5-7: \(N \le 200\)
• Тести 8-16: Немає додаткових обмежень.