АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

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

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

Input

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

Output

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

Example

Input 1:

3

3 1 2

Output 1:

0

Input 2:

2

2 2

Output 2:

1

Input 3:

5
5 3 3 3 1

Output 3:

2