====== گریه‌ی هپید ====== هپیدِ ما باز شروع کرده به گریه کردن‎!‎ احمد هم دلش برای او سوخت و یک مساله طرح کرد تا برای مدتی هپید را سرگرم کند. او یک درخت دودویی‎ (یعنی هر راسی یا دو تا بچه دارد، یا هیچی) ‎$2n-1$‎ راسیِ ریشه‌دار در نظر گرفت. سپس از ریشه درخت یک ‎DFS‎ زد و هرگاه که وارد یک برگ می‌شد، شماره‌ی آن برگ را یادداشت می‌کرد. به این ترتیب پس از پایان یافتن DFS‎، او ‎$n$‎ عدد متفاوتِ ‎$l_1 \ldots l_n$‎ را (به تعداد برگ‌ها) یادداشت کرده بود. احمد ‎$d_i$‎ را برابر فاصله ‎$l_i$‎ از ‎$l_{i+1}$‎ در درخت تعریف کرد (‎تعداد یال‌های بینشون}. به این ترتیب ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎ به وجود آمدند. احمد به هپید، عدد ‎$n$‎، و سپس ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎، و بعد از آن دو عدد ‎$i$‎ و ‎$j$‎ را می‌دهد و به او می‌گوید: ‎»‎اگر فاصله‌ی برگ‌های ‎$l_i$‎ و ‎$l_j$‎ از درخت را به من بگویی، برایت بستنی می‌خرم‎.«‎ الکی بود‎!‎ برنامه‌ای بنویسید که عدد ‎$n$‎ ‎ و ‎$n-1$ عدد ‎$d_1 \ldots d_{n-1}$‎ و دو عدد ‎$i$‎ و ‎$j$‎ را بگیرد و فاصله‌ی ‎$l_i$‎ و ‎$l_j$‎ را در خروجی چاپ کند. ===== ورودی ===== * در سطر اول ورودی عدد ‎$n$‎ آمده است. * در ‎$n-1$‎ سطر بعدی، ‎$n-1$‎ عدد ‎$d_1 \ldots d_{n-1}$‎ آمده است * در سطر آخر دو عدد ‎$i$‎ و ‎$j$‎ داده شده است. * $2 \leq n \leq 10 000$‎. در ‎$60$‎ درصد تست‌ها ‎$n \leq 1000$‎ است. ===== خروجی ===== در تنها سطر خروجی، فاصله‌ی ‎$l_i$‎ و ‎$l_j$‎ را چاپ کنید. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 \\ 3 \\ 2 \\ 1 3 \\ 3 | 3 | * [[سوال ۷|سوال بعد]] * [[سوال ۵|سوال قبل]]