B. Сэлгэлт

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

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

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

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

Поликарпус “Энэ бол даалгавар хийх цаг” гэсээр өөрийн хамгийн дуртай хичээл болох IT гийхаа хичээлийн даалгаварыг хийж эхлэв. Поликарпус хамгийн сүүлчийн бодлогыг 20 минутанд дуусгадаг байв. Поликарпус тодорхой хугацаанд бодлогыг бодох гээд чадахгүй байгаа тул таниас туслалцаа хүсэж байна.

Хэрвээ 1 ээс N хүртэл бүх бүхэл тоонууд яг 1 удаа орсон байвал , 1-ээс N хүртэл тоонынийлбэрийг сэлгэлт гэж нэрлэнэ. Танд дурын бүхэл тоонууд агуулсан $a_1$, $a_2$, ..., $a_n$ дараалал өгөгдсөн. $N$ дарааллын ($a_1$, $a_2$, ..., $a_n$) аль ч бүхэл тоо нь 1-ээс багагүй 5000-ихгүй байна. Сэлгэлт үүсгэхийн туд хамгийн багадаа N дарааллын хэдэн элемэнтийг өөрчлөх хэрэгтэй вэ ? (Тоо нэмж хасаж болохгүй). Элемэнтийг элемэнтээр сольж болно.

Оролт

1-р мөрөнд дараалалд хэдэн элемэнт байгааг харуулах бүхэл тоо $n$ ($1 ≤ n ≤ 5000$)-г агуулна.2-р мөрөнд дарааллын элемэнтүүд $a_i$ ($1 ≤ a_i ≤ 5000, 1 ≤ i ≤ n$) агуулагдана.

Гаралт

Сэлгэлт үүсгэх хамгийн бага тооны өөрчлөлт.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Баттулга

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

Оролт
3
3 1 2
Гаралт
0
Оролт
2
2 2
Гаралт
1
Оролт
5
5 3 3 3 1
Гаралт
2

Тэмдэглэл

The first sample contains the permutation, which is why no replacements are required.

In the second sample it is enough to replace the first element with the number 1 and that will make the sequence the needed permutation.

In the third sample we can replace the second element with number 4 and the fourth element with number 2.

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