АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

a1,a2,…,an массив өгөгдөв. al,al+1,…,ar (1≤l≤r≤n 1≤l≤r≤n)  1/(r−l+1)*∑ai арифметик дундаж нь хамгийн их байх дараалсан сегментийн уртыг ол. 

Input

 Эхний мөрөнд бүхэл тоо n өгөгдөнө. 1<=n<=10⁵.

Хоёр дахь мөрөнд массивын элементүүд болох бүхэл тоо a₁, a₂, ... , a_n өгөгдөнө. 0<=a_i<=10⁹.  

Output

Арифметик дундаж нь хамгийн их байх дэд сегментийн хамгийн урт болох бүхэл тоо.

Example

Input:

5

6 1 6 6 0

Output:

2

Тайлбар :

[3, 4] дэд сегмент нь арифметик дундаж нь хамгийн их хамгийн урт дэд сегмент.