====== Segment Tree ======

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

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

===== محدودیت‌ها =====

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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
| 5 4 \\ 1 2 3 2 1 \\ 1 1 \\ 1 2 \\ 1 5 \\ 1 5 | 1 \\ 2 \\ 2 \\ 5 |
</WRAP>


<پاسخ>
منتظر پر کردن این قسمت توسط علاقمندان هستیم.
</پاسخ>

  * [[سوال ۳۹|سوال بعد]]
  * [[سوال ۳۷|سوال قبل]]