C. Сонирхолтой тоглоом

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

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

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

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

Хоёр сайн найз Серёжа, Гена нар тоглоом тоглож байв.

Эхлээд ширээн дээр $n$ ширхэг чулуу байв. Ѳѳрийн ээлжинд нэг хэсгийг сонгоод дурын байдлаар $a_1>a_2>...>a_k>0$ ширхэг чулуутай хэсгүүдэд хуваана. Уг хэсгүүд нь $a_1-a_2=a_2-a_3=...=a_{k-1}-a_k=1$ нѳхцлийг хангах ёстой. Мэдээж уг хуваах хэсгүүдийн тоо $k$ нь хоёроос багагүй байна.

Найзууд ээлжлэн нүүнэ. Үйлдэл хийж чадахгүй болсон тоглогч хожигдно. Серёжа хамгийн эхний үйлдлийг хийнэ. Хоёр тоглогч хамгийн зѳв тактикаар тоглоход хэн нь хожих вэ?

Оролт

Нэг мѳрѳнд бүхэл тоо $n$ ($1≤n≤10^5$) ѳгѳгднѳ.

Гаралт

Хэрвээ Серёжа хожих бол түүний хожихдоо хийх эхний үйлдэлдээ байж болох хамгийн бага хуваалтын тоо болох $k$ бүхэл тоог хэвлэ.

Хэрвээ Гена хожих бол $-1$ гэж хэвлэ.

Орчуулсан: Sugardorj

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

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