מועדון ריצה מגייס חברים וצומח במהירות, כאשר בדיוק חבר חדש אחד מצטרף בכל יום. כל חבר מגיע עם רמת מיומנות התחלתית מסוימת, ומוקצה לו מזהה ייחודי (ID) על סמך סדר הגעתו.

בסוף כל יום, המאמן אוהב לחשב מדד שהוא מכנה "הפוטנציאל הכולל" של המועדון. ערך זה הוא פשוט סכום הפוטנציאלים האישיים של כל החברים הנוכחיים. כדי לשמור על המוטיבציה של החברים, הפוטנציאל של חבר מחושב באמצעות תרחיש היפותטי של "מה אם" הכולל אימון אינטנסיבי יחיד.

באימון דמיוני זה, חבר יכול לבחור להשקיע כמות מסוימת של מאמץ כדי להעלות באופן זמני את רמת המיומנות שלו. עבור כל $1$ יחידת מאמץ שהוא משקיע, רמת המיומנות שלו עולה בבדיוק $1$ יחידה. בתמורה, הוא מרוויח $1$ יחידת "אושר" עבור כל חבר אחר שנמצא כעת במועדון אשר:

• הצטרף למועדון באופן מובהק אחריו; וכן
• היה במקור בעל מיומנות גבוהה משלו באופן מובהק, אך כעת הושג או נעקף בזכות האימון.

שימו לב שבמהלך חישוב זה, רק רמת המיומנות של אותו חבר עולה, בעוד שרמות המיומנות של כל שאר החברים נשארות קבועות בערכיהן המקוריים.

הפוטנציאל של חבר בודד מוגדר כערך המקסימלי האפשרי של הרווח הנקי שלו (אושר פחות מאמץ) שהוא יכול להשיג על ידי בחירה אופטימלית של רמת המאמץ שלו. אימונים אלה הם תיאורטיים לחלוטין; הם משמשים רק עבור הדו"ח היומי של המאמן, ורמות המיומנות בפועל של החברים נשארות ללא שינוי מיום ליום.

המשימה שלכם היא לעזור למאמן לחשב את הפוטנציאל הכולל של המועדון בסוף כל יום בתקופת הגיוס.

קלט

השורה הראשונה של הקלט מכילה מספר שלם $n$ ($1 \le n \le 10^5$), המייצג את מספר הימים שבהם המועדון מגייס חברים.

השורה השנייה מכילה $n$ מספרים שלמים $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), כאשר $a_i$ היא רמת המיומנות ההתחלתית של החבר שמצטרף ביום $i$.

פלט

הדפיסו $n$ מספרים שלמים בשורה אחת. המספר השלם ה-$k$ צריך להיות הפוטנציאל הכולל של המועדון בסוף יום $k$.

דוגמאות

קלט 1

8
1 2 3 1 2 3 2 3

פלט 1

0 0 0 0 1 3 5 9

קלט 2

1
1

פלט 2

0

הערות

הסבר לדוגמה 1: ביום $5$, ישנם $5$ חברים עם רמות מיומנות $[1, 2, 3, 1, 2]$. עבור חבר $1$: ישנם $3$ חברים שהצטרפו מאוחר יותר עם מיומנויות גבוהות יותר באופן מובהק: חבר $2$, חבר $3$ וחבר $5$. הפוטנציאל המקסימלי עבור חבר $1$ הוא $1$, והוא מושג על ידי אחת מהאסטרטגיות הבאות:

• אם חבר $1$ משקיע $1$ יחידת מאמץ, המיומנות שלו הופכת ל-$2$. הוא ישיג או יעקוף את חבר $2$ ואת חבר $5$. האושר הוא $2$ יחידות, והרווח הוא $2 - 1 = 1$ יחידה.
• אם חבר $1$ משקיע $2$ יחידות מאמץ, המיומנות שלו הופכת ל-$3$. הוא ישיג או יעקוף את חברים $2$, $3$ ו-$5$. האושר הוא $3$ יחידות, והרווח הוא $3 - 2 = 1$ יחידה.

לשאר החברים יש פוטנציאל מקסימלי $0$. לכן, הפוטנציאל הכולל עבור יום $5$ הוא $1$.

ביום $8$, ישנם $8$ חברים עם רמות מיומנות $[1, 2, 3, 1, 2, 3, 2, 3]$. המאמצים האופטימליים הם $[2, 1, 0, 2, 1, 0, 1, 0]$ והפוטנציאלים המקסימליים המתאימים הם $[4, 2, 0, 2, 1, 0, 0, 0]$.