+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه‌ای متشکل از $n$ عدد داریم. یک بازه از این اعداد را **زیبا** می‌نامیم اگر و تنها اگر مجموع اعداد حاضر در این بازه کمتر یا مساوی عدد $k$ و بیشتر یا مساوی عدد $-k$ باشد. به عبارتی دیگر، قدر مطلق مجموع اعداد این بازه باید حداکثر $k$ باشد. روی این آرایه $q$ بار عملیات انجام شده است، هر عملیات به این صورت است که دو عدد $i$ و $x$ مشخص شده‌اند ($1 \le i \le n-1$)، سپس عضو $i$-ام آرایه با عدد $x$ جمع می‌شود و از عضو $i+1$-ام آرایه عدد $x$ تفریق می‌شود. (توجه کنید که مقدار $x$ می‌تواند منفی هم باشد) از شما خواسته شده یکبار در ابتدا و سپس بعد از اعمال هر عملیات، تعداد بازه‌های زیبای آرایه را محاسبه کنید. دقت کنید تمامی عملیات‌ها پایا هستند، یعنی اثر آن‌ها در عملیات‌های بعدی نیز روی آرایه می‌ماند. # ورودی در خط اول ورودی به ترتیب سه عدد $n$، $k$ و $q$ آمده‌اند. در خط دوم $n$ عدد آمده‌اند که اعداد اولیه‌ی آرایه هستند و عدد $i$ را با $a_i$ نمایش می‌دهیم. در $q$ خط بعدی، در هر خط به ترتیب دو عدد $i$ و $x$ آمده‌اند که عملیات را مشخص می‌کنند. $$ 2 \le n \le 100 \, 000 $$ $$ 1 \le q \le 100 \, 000 $$ $$ 0 \le k \le 10 ^ 9$$ $$ -10 ^ 9 \le a_i, x \le 10 ^ 9$$ $$ 1 \le i \le n - 1 $$ همچنین تضمین می‌شود **قدر مطلق** تمامی اعداد آرایه بعد از هر کوئری حداکثر $10^9$ خواهد ماند. # خروجی خروجی شما باید شامل $q+1$ خط باشد که نشان دهد در ابتدا و بعد از انجام هر عملیات تعداد بازه‌های زیبای آرایه چقدر است. # مثال ## ورودی نمونه ۱ ``` 5 3 2 1 2 3 4 5 3 -2 2 4 ``` ## خروجی نمونه ۱ ``` 4 5 4 ``` در این نمونه در ابتدا بازه‌های $[1]$، $[2]$، $[3]$ و $[1,2]$ زیبا هستند. بعد از عملیات اول آرایه تبدیل می‌شود به: $1, 2, 1, 6, 5$. بعد از این تغییر بازه‌های $[1]$، $[2]$، $[3]$، $[1,2]$ و $[2,3]$ زیبا خواهند بود. بعد از عملیات دوم آرایه به این صورت خواهد بود: $1, 6, -3, 6, 5$. بعد از این تغییر بازه‌های $[1]$، $[3]$، $[2,3]$ و $[3,4]$ زیبا هستند. (منظور از بازه‌ی $[i,j]$ بازه‌ای است که از عضو $i$ام شروع شده و تا عضو $j$ام ادامه دارد) ## ورودی نمونه ۲ ``` 5 5 5 -3 -4 0 5 -5 2 1 2 3 4 -4 2 -1 3 5 ``` ## خروجی نمونه ۲ ``` 12 12 13 12 12 13 ``` ## ورودی نمونه ۳ ``` 7 5 10 -10 11 -15 -8 6 8 8 2 -16 6 -7 2 13 2 -18 4 -6 3 -8 4 10 5 7 2 -2 6 17 ``` ## خروجی نمونه ۳ ``` 6 7 10 8 9 8 6 10 8 7 7 ```

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