Trái dấu

Cho một dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Với mỗi vị trí \(i\) (\(1 \le i \le n\)), hãy tìm độ dài lớn nhất của một đoạn con liên tiếp bắt đầu tại \(i\) sao cho các phần tử liên tiếp trong đoạn đó trái dấu nhau.

Hai số được gọi là trái dấu nếu một số âm và số kia dương. Một đoạn con \((i..j)\) của \(a\) là một dãy các phần tử liên tiếp nhau \(a_i,a_{i+1},\cdots,a_j\) (\(i \le j \le n\)).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(-10^5 \le a_i \le 10^5\) và \(a_i \ne 0\)).

Output

In ra \(n\) số nguyên, số thứ \(i\) là độ dài lớn nhất của đoạn trái dấu liên tiếp bắt đầu từ vị trí \(i\).

Scoring

• Có 50% số điểm ứng với \(n \le 10^3\).
• 50% số điểm còn lại ứng với \(n \le 10^5\).

Sample Input 1

5
1 -2 3 -4 5

Sample Output 1

5 4 3 2 1 

Sample Input 2

6
1 -2 -3 3 -4 5

Sample Output 2

2 1 4 3 2 1