تجاوز العداؤون في سباق للمسافات الطويلة نقطة العودة. لكل عداء قيمة قدرة صحيحة تختلف عن قيم بقية العدائين؛ وتشير القيمة الأكبر إلى عداء أقوى. يستطيع العداء تجاوز أي عداء أمامه ذي قدرة أقل، لكنه لا يستطيع تجاوز عداء أقوى منه.

بمعرفة القدرات مرتبة بحسب الترتيب الحالي للسباق، من المقدمة إلى المؤخرة، أوجد أفضل مركز يستطيع كل عداء تحقيقه.

على سبيل المثال، تعطي القدرات $2,8,10,7,1,9,4,15$ أفضل المراكز $1,1,1,3,5,2,5,1$. يستطيع العداء الرابع، ذو القدرة $7$، تجاوز العداء ذي القدرة $2$، لكنه لا يستطيع تجاوز العداءين ذوي القدرتين $8$ و$10$، ولذلك يكون أفضل مركز له هو $3$.

الإدخال

يحتوي السطر الأول على $N$ ($3 \le N \le 500000$). ويحتوي كل سطر من الأسطر $N$ التالية على قدرة عداء واحد، بحسب الترتيب الحالي للسباق. القدرات أعداد صحيحة مختلفة من $1$ إلى $10^9$ شاملًا.

الإخراج

اطبع $N$ سطرًا بحسب ترتيب الإدخال، يبيّن كل منها أفضل مركز للعداء المقابل. المركز 1 هو المركز الأول.

أمثلة

الإدخال 1

8
2
8
10
7
1
9
4
15

الإخراج 1

1
1
1
3
5
2
5
1