Segment Tree

یک دنباله $n$ تایی از اعداد داریم. در هر مرحله یک بازه متوالی از این دنباله را انتخاب کرده و ماکسیمم آن را به‌دست می‌آوریم. بعد تمام اعداد بازه را برابر ماکسیمم قرار می‌دهیم. هم‌چنین اگر تمام اعداد بازه برابر ماکسیمم بودند به همه یک واحد اضافه می‌کنیم.

• در خط اول دو عدد $n$ و $q$ آمده است.
• در خط دوم $n$ عدد آمده که نمایانگر اعداد اولیه دنباله‌اند. (تمام اعداد این خط بین $0$ و$10^9$ اند)
• در $q$ خط بعد در هر خط دو عدد $L$ و $R$ آمده است که به معنی انتخاب بازه‌ی [$L$, $R$] است.
• $1 \leq n, q \leq 10^5$

به ازای هر یک از $q$ مرحله، در یک خط تعداد اعدادی که مقدارشان تغییر کرده‌است را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل