ﺩﺭ ﮐﻮﻫﺴﺘﺎﻥﻫﺎﯼ ﯾﻮﺗﻮﭘﯿﺎ ﺩﺭ ﮐﺸﻮﺭ ﺍﻟﻤﭙﯿﺎﺩﯼﻫﺎ $n$ ﮐﻮﻩ ﺑﻪ ﺗﺮﺗﯿﺐ ﺩﺭ ﯾﮏ ﺭﺩﯾﻒ ﻗﺮﺍﺭ ﺩﺍﺭﻧﺪ. ﺍﺭﺗﻔﺎﻉ کوه $i$ام $h_i$ می‌باشد. باشگاه دانش‌پژوهان جوان در صدد ساخت یک ﺗﻠﻪﮐﺎﺑﯿﻦ ﺩﺭ ﺍﯾﻦ ﮐﻮﻫﺴﺘﺎﻥ ﻣﯽﺑﺎﺷﺪ. ﺍﯾﻦ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺩﻭ ﺳﺮ ﺩﺍﺭﺩ ﮐﻪ ﺗﻮﺳﻂ ﯾﮏ ﺳﯿﻢ ﺭﺍﺳﺖ ﺑﻪ ﻫﻢ ﻣﺘﺼﻞ ﻣﯽﺑﺎﺷﻨﺪ. ﺍﯾﻦ ﺩﻭ ﺳﺮ ﺑﺎﯾﺪ ﺭﻭﯼ ﺩﻭ ﮐﻮﻩ ﻣﺘﻔﺎﻭﺕ ﺳﺎﺧﺘﻪ ﺷﻮﻧﺪ. ﻫﻤﭽﻨﯿﻦ ﺩﻭ ﺳﺮ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺑﺎﯾﺪ ﻫﻢﺍﺭﺗﻔﺎﻉ ﺑﺎﺷﻨﺪ. ﺩﺭ ﻧﺘﯿﺠﻪﯼ ﺳﺎﺧﺖ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺭﻭﯼ ﮐﻮﻩﻫﺎﯼ $i$ام و $j$ام تنها در صورتی ممکن است که تمامی کوه‌های $i$ام تا $j$ام (شامل خود کوه $i$ و $j$) ارتفاعشان به $min(h_i,h_j)$ کاهش یابد. بدیهی است کوهی که ارتفاعش ﺍﺯ ﺍﯾﻦ ﻣﻘﺪﺍﺭ کم‌تر ﺍﺳﺖ ﻣﺸﮑﻠﯽ ﺍﯾﺠﺎﺩ ﻧﻤﯽﮐﻨﺪ.

ﺍﺩﺍﺭﻩ ﺭﺍﻩﺳﺎﺯﯼ ﺍﻟﻤﭙﯿﺎﺩﯼﻫﺎ ﺑﻪ ﺑﺎﺷﮕﺎﻩ ﻗﻮﻝ ﺩﺍﺩﻩ ﺑﻪ ﺍﺯﺍﯼ ﻫﺰﯾﻨﻪ $p$ تومان می‌تواند $p$ متر از ارتفاع یک کوه را کم کند.

ﺑ‰ﺮﺍﯼ این‌که ﺍﯾ‰ﻦ ﺗ‰ﻠ‰ﻪﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺑ‰ﺮﺍﯼ ﺑ‰ﭽ‰ﻪﻫ‰ﺎ ﺟ‰ﺬﺍﺏ ﺑ‰ﺎﺷ‰ﺪ، ﺑ‰ﺎﺷ‰ﮕ‰ﺎﻩ ﻗ‰ﺼ‰ﺪ ﺩﺍﺭﺩ ﺍﯾ‰ﻦ ﺗ‰ﻠ‰ﻪﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺭﺍ ﻃ‰ﻮﺭﯼ ﺑ‰ﺴ‰ﺎﺯﺩ ﮐ‰ﻪ ﺍﺯ ﺭﻭﯼ ﺣ‰ﺪﺍﻗ‰ﻞ $k$ کوه (با احتساب ﺩﻭ ﮐ‰ﻮﻫ‰ﯽ ﮐ‰ﻪ ﺗ‰ﻠ‰ﻪ ﮐ‰ﺎﺑ‰ﯿ‰ﻦ ﺑ‰ﺮ ﺭﻭﯼ ﺁﻥﻫ‰ﺎ ﺳ‰ﺎﺧ‰ﺘ‰ﻪﺷ‰ﺪﻩ ﺍﺳﺖ) ﻋﺒﻮﺭ ﮐﻨﺪ.

ﺑ‰ﻪ ﺑ‰ﺎﺷ‰ﮕ‰ﺎﻩ ﮐ‰ﻤ‰ﮏ ﮐ‰ﻨ‰ﯿ‰ﺪ ﺑ‰ﺎ کم‌ترین ﻫ‰ﺰﯾ‰ﻨ‰ﻪ ﻣ‰ﻤ‰ﮑ‰ﻦ ﻃ‰ﻮﺭﯼ ﺍﯾ‰ﻦ ﮐ‰ﻮﻩﻫ‰ﺎ ﺭﺍ ﮐ‰ﻮﺗ‰ﺎﻩ ﮐ‰ﻨ‰ﺪ، ﮐ‰ﻪ ﺑ‰ﺘ‰ﻮﺍﻧ‰ﺪ ﯾ‰ﮏ ﺗﻠﻪﮐﺎﺑﯿﻦ ﮐﻪ ﺍﺯ ﺭﻭﯼ ﺣﺪﺍﻗﻞ $k$ کوه ﻋﺒﻮﺭ ﻣﯽﮐﻨﺪ، ﺑﺴﺎﺯﺩ.

ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﻭﺭﻭﺩﯼ $n$ و $k$ آمده است.($1\leq n \leq 3\times 10^5$ و $1\leq k \leq n$)

در سطر بعدی، $n$ عدد آمده که عدد $i$ام ارتفاع کوه $i$ام را مشخص می‌کند.

ﺩﺭ ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮﻭﺟﯽ کم‌ترین ﻫﺰﯾﻨﻪ ﻻﺯﻡ ﺑﺮﺍﯼ ﺳﺎﺧﺖ ﺍﯾﻦ ﺗﻠﻪﮐﺎﺑﯿﻦ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ.

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

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