توجد $N$ مدينة في مملكة JOI، مرقمة بالأعداد من $1$ إلى $N$. المدينة $1$ هي العاصمة. لكل مدينة قيمة تسمى الحيوية، والقيمة الأولية لحيوية المدينة $i$ ($1\le i\le N$) هي $C_i$.

يربط كل طريق في مملكة JOI مدينتين مختلفتين في الاتجاهين. في البداية، لا توجد أي طرق في المملكة. لقد خططت لبناء $N-1$ طريقًا. ستُنفذ عملية البناء ذات الرقم $j$ ($1\le j\le N-1$) بالطريقة التالية:

• تُحدد مدينتان $A_j$ و$B_j$، بحيث يمكن الوصول من المدينة $1$ إلى المدينة $A_j$، ولا يمكن الوصول من المدينة $1$ إلى المدينة $B_j$، باستخدام الطرق المبنية حتى ذلك الوقت فقط.
• تبني طريقًا يربط المدينة $A_j$ بالمدينة $B_j$. تكلفة هذا البناء هي عدد أزواج المدن $(s,t)$ التي تحقق الشروط التالية:

تقع المدينتان $s$ و$t$ على أقصر مسار بين المدينة $1$ والمدينة $A_j$، وعند الانتقال من المدينة $1$ إلى المدينة $A_j$ نصل إلى المدينة $s$ قبل المدينة $t$، وتكون قيمة حيوية المدينة $s$ أكبر تمامًا من قيمة حيوية المدينة $t$.

هنا، تشمل المدن الواقعة على المسار بين المدينة $1$ والمدينة $A_j$ كلًا من المدينة $1$ والمدينة $A_j$. لاحظ أن أقصر مسار بين المدينة $1$ والمدينة $A_j$ وحيد.

• تتغير قيم حيوية جميع المدن الواقعة على المسار بين المدينة $1$ والمدينة $A_j$ لتصبح مساوية لقيمة حيوية المدينة $B_j$.

تريد معرفة تكلفة كل عملية بناء.

المهمة

اكتب برنامجًا يحسب تكلفة كل عملية بناء، عند إعطائه بيانات المدن وعمليات بناء الطرق.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على عدد صحيح $N$، ويعني ذلك أن مملكة JOI تضم $N$ مدينة.
• يحتوي السطر الثاني على $N$ عددًا صحيحًا مفصولة بمسافات، $C_1,C_2,\ldots,C_N$. ويعني ذلك أن القيمة الأولية لحيوية المدينة $i$ ($1\le i\le N$) هي $C_i$.
• يحتوي السطر $j$ ($1\le j\le N-1$) من الأسطر الـ$N-1$ التالية على عددين صحيحين مفصولين بمسافة، $A_j,B_j$. ويعني ذلك أن المدينتين $A_j$ و$B_j$ محددتان لعملية بناء الطريق ذات الرقم $j$.

الإخراج

اكتب $N-1$ سطرًا إلى الإخراج القياسي. يجب أن يحتوي السطر $j$ ($1\le j\le N-1$) على تكلفة عملية بناء الطريق ذات الرقم $j$.

القيود

تحقق جميع بيانات الإدخال الشروط التالية.

• $1\le N\le 100\,000$.
• $1\le C_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $1\le A_j\le N$ ($1\le j\le N-1$).
• $1\le B_j\le N$ ($1\le j\le N-1$).
• باستخدام الطرق المبنية قبل عملية البناء ذات الرقم $j$، يمكن الوصول من المدينة $1$ إلى المدينة $A_j$، ولا يمكن الوصول من المدينة $1$ إلى المدينة $B_j$ ($1\le j\le N-1$).

المهام الفرعية

توجد 3 مهام فرعية. فيما يلي نقاط كل مهمة فرعية وقيودها الإضافية:

المهمة الفرعية 1 [7 نقاط]

• $N\le 500$.

المهمة الفرعية 2 [9 نقاط]

• $N\le 4000$.

المهمة الفرعية 3 [84 نقطة]

لا توجد قيود إضافية.

أمثلة

الإدخال 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

الإخراج 1

0
0
0
2

ملاحظة

في المثال الأول، تُنفذ عمليات البناء كما يلي:

• في عملية البناء الأولى، لا يوجد أي زوج $(s,t)$ يحقق الشروط، لذا تكون التكلفة $0$. يُبنى طريق يربط المدينة $1$ بالمدينة $2$، وتتغير قيمة حيوية المدينة $1$ إلى $2$.
• في عملية البناء الثانية، لا يوجد أيضًا أي زوج $(s,t)$ يحقق الشروط، لذا تكون التكلفة $0$. يُبنى طريق يربط المدينة $2$ بالمدينة $3$، وتتغير قيمتا حيوية المدينتين $1$ و$2$ إلى $3$.
• في عملية البناء الثالثة، لا يوجد أيضًا أي زوج $(s,t)$ يحقق الشروط، لذا تكون التكلفة $0$. يُبنى طريق يربط المدينة $2$ بالمدينة $4$، وتتغير قيمتا حيوية المدينتين $1$ و$2$ إلى $4$.
• في عملية البناء الرابعة، يحقق الزوجان $(s,t)=(1,3),(2,3)$ الشروط، لذا تكون التكلفة $2$. يُبنى طريق يربط المدينة $3$ بالمدينة $5$، وتتغير قيم حيوية المدن $1$ و$2$ و$3$ إلى $5$.

الإدخال 2

10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10

الإخراج 2

0
0
0
1
1
0
1
2
3