+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مارچلو که از سپری کردن تابستان خود در یک مسافرت رویایی داشت نهایت لذت را می‌برد، تصمیم گرفت که ورزشی را به طور حرفه‌ای شروع کند و چه ورزشی بهتر از پرش با دنباله! مارچلو دو دنباله‌ی $n$ تایی از اعداد صحیح دارد که عضو $i$اُم دو دنباله را به ترتیب با $a_i$ و $b_i$ نشان می‌دهیم. او می‌خواهد ابتدا دنباله‌ی پرش‌های خود را بدست بیاورد و سپس اقدام به پرش کند. دنباله‌ی $<d_{1},\,d_{2},\,...,\,d_{k}>$ را یک **دنباله‌ی پرش** می‌گوییم، اگر: + $k \le n$ + $1 \le d_i \le n$ + $\forall_{i<j}\,d_{i}\neq d_{j}$ به دنباله‌ی پرش $<d_{1},\,d_{2},\,...,\,d_{k}>$ یک **دنباله‌ی پرش معتبر** می‌گوییم، اگر: + $a_{d_i} \le a_{d_{i+1}}$ + $\left|a_{d_{i}}-a_{d_{i+1}}\right|\leq\left|b_{d_{i}}-b_{d_{i+1}}\right|$ مارچلو که سخت عزم خود را برای حرفه‌ای شدن در این ورزش جزم کرده بود، از شما می‌خواهد که بلندترین دنباله‌ی پرش معتبر در دو دنباله‌ی داده شده را به او گزارش دهید، تا طبق آن پرش‌های خود را انجام دهد. # ورودی ورودی شامل سه خط است که در خط اول، عدد طبیعی $n$ آمده است و در خط دوم $n$ عدد با فاصله از هم آمده است که عدد $i$اُم نشان‌دهنده‌ی $a_i$ است. در خط سوم نیز $n$ عدد با فاصله از هم آمده است که عدد $i$اُم، نشان‌دهنده‌ی $b_i$ است. $$1 \le n \le 100\ 000$$ $$1 \le a_i, b_i \le 100\ 000$$ **تضمین می‌شود $a_i$ها متمایز هستند.** # خروجی در تنها خط خروجی، طول بلندترین دنباله‌ی پرش معتبر را چاپ کنید. ## ورودی نمونه ۱ ``` 3 2 1 3 4 5 9 ``` ## خروجی نمونه ۱ ``` 3 ``` دنباله‌ی $<2,\,1,\,3>$ بلندترین دنباله‌ی پرش معتبر است. ## ورودی نمونه ۲ ``` 5 5 1 6 2 3 9 3 1 4 4 ``` ## خروجی نمونه ۲ ``` 4 ``` دنباله‌ی $<2,\,4,\,1,\,3>$ بلندترین دنباله‌ی پرش معتبر است.

حل سؤال در بانک سؤالات