B. Тогтмол завсарт дөхөж очих

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эксэллос их сургууль дээрээ курсийн дадлага хийж байхдаа нэгэн удаа удаанаар тэнцвэртэй байдал уруу тэмүүлж байгаа үр нөлөөний эрчийг хэмжиж үзжээ.Тэнцвэртэй байдлын эрчийг тодорхойлох сайн арга бол аль болох тогтмол хангалттай их тооны дараалсан өгөгдлийн цэгүүдийг сонгох ба тэдгээрийн дундаж утгыг авч үзэх юм.Мэдээж хэрэг ердийн хэмжээний өгөгдөл байвал энэ нь хүч сориод байх зүйлгүй юм -- гэхдээ бид яагаад уг бодлогыг хөндөх төстэй программ бичиж болохгүй гэж?

Танд $n$ ширхэг өгөгдлийн цэгүүдийн дараалал $a_{1}, ..., a_{n}$ өгөгдөнө.Дараалсан өгөгдлийн цэгүүдийн хооронд ямар нэг том зөрүү байхгүй -- $1 ≤ i < n$ бүрийн хувьд $|a_{i + 1} - a_{i}| ≤ 1$ байх юм.

Хэрэв ямар нэг завсар дахь хамгийн их болон хамгийн бага утгын зөрүү нь хамгийн ихдээ $1$ байвал уг өгөгдлийн цэгүүдийн завсар $[l, r]$-г бараг тогтмол гэж хэлнэ.

Албан ёсоор, $l ≤ i ≤ r$ байх $a_{i}$-уудын $M$-ээр хамгийн их ба $m$-ээр хамгийн утгыг тэмдэглэх ба, хэрэв $M - m ≤ 1$ байвал $[l, r]$ завсрыг бараг тогтмол гэж хэлэх юм.

Тэгвэл хамгийн урт бараг тогтмол завсрыг олно уу.

Оролт

Эхний мөрөнд өгөгдлийн цэгийн тоог илэрхийлэх ганц бүхэл тоо $n$ ($2 ≤ n ≤ 100 000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 100 000$)-ууд өгөгдөнө.

Гаралт

Өгөгдсөн дарааллын бараг тогтмол завсруудын уртын хамгийн их утгыг илэрхийлэх ганц тоог хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5
1 2 3 3 2
Гаралт
4
Оролт
11
5 4 5 5 6 7 8 8 8 7 6
Гаралт
5

Тэмдэглэл

Эхний жишээнд, хамгийн урт бараг тогтмол завсар нь $[2, 5]$ бөгөөд үүний урт нь(үүн дээр байгаа өгөгдлийн цэгийн тоо) 4 байх юм.

2-дахь жишээнд, $4$ урттай 3-н ширхэг бараг тогтмол завсар байна:$[1, 4]$, $[6, 9]$ болон $[7, 10]$; цорын ганц хамгийн их урт буюу $5$ урттай бараг тогтмол завсар нь $[6, 10]$ байх юм.

Сэтгэгдлүүдийг ачааллаж байна...