Masala A

Qodirali o‘zini haqiqiy raqamlar sehrgari deb biladi va har safar yangi sonli o‘yinlarni kashf etishni yoqtiradi. Bugun esa u qo‘lida uzunligi \(n\) bo‘lgan 0-indeksli \(arr\) massiv bilan o‘ynayapti.

Siz \([0, n-1]\) oraliqdan \(k\) ta son ( \(k \ge 2\) ) tanlaysiz. Qoidaga ko‘ra, tanlagan sonlaringiz orasida \(0\) va \(n-1\) albatta bo‘lishi kerak.

Qodirali tanlagan indeklaringizdan yangi \(ind\) massiv tuzadi. Endi, bu massiv yordamida u o‘zining maxsus «qiziqarli qiymat»ini quyidagicha hisoblaydi:

Sizning vazifangiz – shunday indekslar to‘plamini tanlash kerakki, hosil bo‘ladigan \(s\) maksimal qiymatga ega bo‘lsin. Eng kattasini toping va ekranga chiqaring!

1-qatorida \(n\) soni. \(2 \le n \le 10^5\)

2-qatorida \(n\) ta sonli \(arr\) massiv kiritiladi. \(1 \le arr[i] \le 10^9\)

Eng maksimal \(s\) ni chiqaring.