• محدودیت زمان:‌ ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

به تعداد $n$ بادکنک در یک ردیف قرار دارند. رنگ بادکنک $i$ام $a_i$ است. در ابتدای هر روز همزمان بادکنک‌های هر دسته از بادکنک‌های پشت سر هم و هم رنگ که شامل حداقل ۳ بادکنک باشد می‌ترکند و در پایان هر روز بادکنک‌های باقی‌مانده دوباره در یک ردیفِ پیوسته با همان ترتیب قرار می‌گیرند. می‌خواهیم بدانیم هر بادکنک در چه روزی می‌ترکد.

ورودی

در خط اول ورودی عدد $n$ آمده است که تعداد بادکنک‌ها را نشان می‌دهد.

$$1 \le n \le 300\ 000$$

$$1 \le a_i \le 10^9$$

خروجی

به ازای هر بادکنک روز ترکیدنش را چاپ کنید، اگر یک بادکنک هیچ‌گاه نمی‌ترکد -1 را چاپ کنید.

مثال

ورودی نمونه

7
1 2 2 3 3 3 2

خروجی نمونه

-1 2 2 1 1 1 2

ورودی نمونه

20
2 2 2 1 1 2 2 1 2 1 2 1 1 2 2 2 1 2 2 2

خروجی نمونه

1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 1 1 1 2 1 1 1