D. Хамгийн бага хувьсагчдын тоо

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

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

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

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

Танд бүхэл тоон $a_1,\ a_2,...,\ a_n$ дараалал өгөгджээ. Дарааллын бүх гишүүд ялгаатай байна. Олонлогийн $b_1$, $b_2$,..., $b_m$ хувьсагчуудыг засацгаая. Эхэндээ бүх $b_i$ $(1≤i≤m)$ хувьсагч $0$ утгатай байсан. Дараах $n$ үйлдэлтэй дарааллыг авч үзье.

Эхний үйлдэл нь $a_1$-ийн утгыг $b_x\ (1≤x≤m)$-д өгнө. Дараах $n-1$ үйлдэл нь $b_y$-д $b_i$ болон $b_j$ $(1≤i,j,y,≤m)$-ийн нийлбэрийг өгнө. Үүнд $t$-р үйлдэл дээр өгөгдсөн утга $a_t$-тэй тэнцүү байх ёстой. Үйлдэл бүр дээр $y,\ i,\ j$ тоонууд шихээр сонгогдоно.

Таны даалгавар бол хамгийн бага $m$ хувьсагчдийн тоог олох юм.

Оролт

Эхний мөрөнд дарааллын гишүүдийн тоо $n(1 ≤ n ≤ 23)$ байна. Хоёрдугаар мөрөнд дарааллын гишүүд болох $a_1$, $a_2$,..., $a_n$ $(1 ≤ a_i ≤ 10^9)$ өгөгдөнө.

Дарааллын бүх гишүүд хоорондоо ялгаатай байна.

Гаралт

Бодлогын хариу болох хамгийн бага хувьсагчийн $m$ тоог хэвлэнэ. Хэрвээ тийм тоо олдохгүй бол $-1$ гэж хэвлэнэ.

Орчуулсан: Говьхүү

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

Оролт
5
1 2 3 6 8
Гаралт
2
Оролт
3
3 6 5
Гаралт
-1
Оролт
6
2 4 8 6 10 18
Гаралт
3

Тэмдэглэл

In the first sample, you can use two variables $b_{1}$ and $b_{2}$ to perform the following sequence of operations.

  1. $b_{1}$ :=$ $1$;
  2. $b_{2}$ :=$ $b_{1} + b_{1}$;
  3. $b_{1}$ :=$ $b_{1} + b_{2}$;
  4. $b_{1}$ :=$ $b_{1} + b_{1}$;
  5. $b_{1}$ :=$ $b_{1} + b_{2}$.
Сэтгэгдлүүдийг ачааллаж байна...