C. Бараг л арифметик прогресс

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

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

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

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

Жена тоон дараалалд маш их дуртай. Саяхан тэрээр шинэ дараалал бодож олоод түүнийгээ бараг л арифметик прогресс гэж нэрлэжээ. Дарааллын элементүүд нь дараах байдлаар өгөгдсөн бол уг дараалал нь бараг л арифметик прогресс болно. Үүнд:

  • $a_{1} = p$, энд $p$ нь ямар нэг бүхэл тоо;
  • $a_{i} = a_{i - 1} + ( - 1)^{i + 1}*q$ $(i > 1)$, энд $q$ нь ямар нэг бүхэл тоо.

Одоо Жена $n$ ширхэг бүхэл тооноос бүрдсэн $b$ дараалал бичигдсэн цаасыг харж байна. Бараг л арифметик прогресс байх, хамгийн урт бүхэл тоон дэд дарааллыг олоход Женад туслаарай.

$b_{i_{j}}  =  s_{j}$ байх $i_{1}, i_{2}, ..., i_{k}$ дугааруудын дараалал өсч байвал (өөрөөр хэлбэл $1  ≤  i_{1}  <  i_{2}  < ...   <  i_{k}  ≤  n$) $s_{1},  s_{2},  ...,  s_{k}$ дараалал нь $b_{1},  b_{2},  ...,  b_{n}$ дарааллын дэд дараалал байна. Өөрөөр хэлбэл, $b$-ээс зарим элементийг нь хассанаар $s$ дэд дараалал үүснэ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 4000)$ байна. Дараагийн мөр нь $n$ ширхэг $b_{1}, b_{2}, ..., b_{n}$ $(1 ≤ b_{i} ≤ 10^{6})$ бүхэл тоонуудыг агуулна.

Гаралт

Шаардлага хангах хамгийн урт дэд дарааллын уртыг илэрхийлсэн нэг тоо.

Орчуулсан: Солонго

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

Оролт
2
3 5
Гаралт
2
Оролт
4
10 20 10 30
Гаралт
3

Тэмдэглэл

Эхний жишээнд өгөгдсөн дараалал нь өөрөө шаардлага хангасан дэд дараалал болох боломжтой байна.

2 дахь жишээнд дараах дэд дараалал тохирно: $[10, 20, 10]$.

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