D. Хүн амын тооллого

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

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

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

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

Поликарпус дэлхий дээрх бүх эд зүйлсийн тоонууд арифметик прогрессоос бүтдэг гэсэн онол томьёолсон бөгөөд одоогоор энэ онолынхоо дагуу Бэрландын нийслэлийн хүн амын өсөлтийн график нь хэд хэдэн арифметик прогрессийн нийлмэл бүтэцтэй гэсэн дүгнэлт хийчихээд байгаа юм.

Хэрвээ жил болгоны нийслэлийн хүн амын хэмжээг тоон дараалал $a_{1}, a_{2}, ..., a_{n}$ болгон бичвэл үүнийг хэд хэдэн арифметик прогресс болгон хуваахад илүү амархан болно гэж Поликарпус үзжээ. Жишээ нь: $(8, 6, 4, 2, 1, 4, 7, 10, 2)$ гэсэн тоон дараалал нь $(8, 6, 4, 2)$, $(1, 4, 7, 10)$, $(2)$ гэсэн 3-н ширхэг арифметик прогресс болж чадна.

Харамсалтай нь Поликарпусд $n$ ширхэг дараалсан жилийн хүн амын тооллогын бүрэн дүн байхгүй. Учир нь жил болгон хүн амын тооллого болдоггүй. Үүнээс болоод зарим $a_{i}$ нь мэдэхгүй бөгөөд эдгээрийг тоон дараалал дотор $-1$-ээр тэмдэглэжээ.

Тоон дарааллын байр нь солигдохгүй бол бүхэл эерэг тоонууд болон $-1$-ээс бүтсэн $a = (a_{1}, a_{2}, ..., a_{n})$ дараалалд хамгийн багадаа хэдэн ширхэг арифметик прогресс байх боломжтой вэ? Энэ дарааллын $-1$-ийн оронд дурын эерэг бүхэл тоо орлуулан арифметик прогресс үүсгэх боломжтой. Цөөн тооны арифметик прогресс үүсгэхийн тулд $-1$-ийг өмнөх эсвэл арын тоонуудтай нийлэн арифметик прогресс үүсгэх байдлаар өөрт ашигтай тоогоор орлуулах нь зөв юм.

Хэрвээ дараалсан $2$ тооны зөрүү $(c_{i + 1} - c_{i})$ цаашид өөрчлөгдөхгүй байвал зөрүү өөрчлөгдөх хүртэлх тоог $c$ арифметик прогресс гэж нэрлэнэ. $1$ урттай ямар ч дараалал арифметик прогресс болох боломжтой.

Оролт

Эхний мөрөнд дарааллын элементийн тоо ширхэг буюу бүхэл тоо $n$ ($1 ≤ n ≤ 2 \cdot 10^{5}$) өгөгдөнө. Дараагийн мөрөнд бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$ эсвэл $a_{i} = -1$) зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

$a$ тоон дарааллаас элементүүдийн байр нь өөрчлөгдөхгүй үед үүсч болох арифметик прогрессийн хамгийн бага тоог хэвлэнэ. Дараалал дотор буй "-1"-ийг дурын бүхэл эерэг тоогоор орлуулж болно.

Орчуулсан: Энхлут

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

Оролт
9
8 6 4 2 1 4 7 10 2
Гаралт
3
Оролт
9
-1 6 -1 2 -1 4 7 -1 2
Гаралт
3
Оролт
5
-1 -1 -1 -1 -1
Гаралт
1
Оролт
7
-1 -1 4 5 1 2 3
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...