D. Аврагч

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

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

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

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

Миша Паша, Аким нарт туслахаар шийдсэн ба тэд нартай ахин найзууд болов. Түүнд бүх инээмтгий мөөгийг устгах зальтай төлөвлөгөө байлаа. Тэр инээмтгий мөөгийг инээж байхад нь сугалах амархан гэдгийг мэддэг. Мөөгнүүд зүлгэн дээр ургасан байв. $t$-р зүлгэн дээр $a[t]$ ширхэг мөөг байна.

Миша эдгээр зүлгэн дээрх мөөгнүүд ганц удаа л ургадаг гэдгийг мэднэ. Хэрвээ $a[i]$, $a[j]$, $b$ (энд $i ≠ j$) тоонуудын ямар нэг сэлгэмэл гоё гурвал үүсгэдэг байх $(say, b)$ бүхэл тоо олддог бол $(say, i)$ зүлэг $(say, j)$ зүлэг рүү инээд дамжуулж чадна. Хос хосоороо харилцан анхны $x$, $y$, $z$ тоонуудын хувд $x^2 + y^2 = z^2$ нөхцөл биелдэг бол гоё гурвал гэнэ.

Миша хамгийн цөөндөө хэдэн зүлгийг инээлгээд бүх инээмтгий мөөгийг сугалж болохыг мэдэхийг хүсэв.

Оролт

Эхний мөр зүлэгний тоо болох $n$ ($1 ≤ n ≤ 10^6$) бүхэл тоог агуулна. Дараагийн мөр $n$ ширхэг, $i$-р зүлгэн дээрх мөөгний тоо болох $a_i$ ($1 ≤ a_i ≤ 10^7$) бүхэл тоонуудыг агуулна. Эдгээр тоонууд ялгаатай байна.

Гаралт

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

Орчуулсан: Sugardorj

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

Оролт
1
2
Гаралт
1
Оролт
2
1 2
Гаралт
2
Оролт
2
3 5
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...