B. Олон зэрэг унших

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

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

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

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

Эмукалд Codeforces-д донтсон ба "саяхан болсон үйл явдал"-ын бүртгэлийг алдалгүй харахын тулд дахин дахин үндсэн хуудсыг уншуулсаар байдаг. Тэрээр чат бүр нь олон тооны захианаас тогтох чатын харилцан яриануудыг унших дуртай.

Саяхан болсон үйл явдлууд нь тухайн чатуудын сүүлд ирсэн захианы цагаар дараалуулсан $n$ ширхэг чатын бүртгэлийг харуулдаг. Ямар нэгэн чатад шинэ захиа ирэхэд тухайн чат нь уг бүртгэлийн хамгийн дээр гарч ирнэ. Ялгаатай чатуудын ямар ч 2 захиа нь нэгэн зэрэг ирдэггүй.

Эмукалд өөрийн нээлттэй бүх чатуудаа саяхан уншиж дууссан ба өөрийн донтолтоосоо болж дахин өөр захианууд уншихын тулд тус сайтын үндсэн хуудсыг дахин уншуулав. Тэрээр ямар ч шинэ чат уг бүртгэлд гарж ирээгүй болохыг мөн уг үндсэн хуудсыг дахин уншуулахаас өмнөх бүртгэлийн $a_{i}$-дахь байрлалд байсан чат $i$-дахь байрлалд байхыг анзаарчээ. Тэрээр хуучин захиануудыг уншиж цагаа үрмээргүй байгаа тул зөвхөн шинэ захианууд бүхий чатууд уруу орж үзэхийг хүсэж байгаа юм.

Эмускалд туслан баттай шинэ захиануудтай болсон чатуудын тоог олж өгнө үү. Хэрэв дараах 2 нөхцөлийг хангах чатын шинэчлэлтүүдийн (шинэ захианууд ирнэ гэсэн үг) дараалал байхгүй бол $x$ чатыг баттай шинэ захиатай байна гэж үзнэ:

  1. $x$ чат нь шинэчлэгдээгүй (ямар ч шинэ захиагүй);
  2. бүртгэлийн дараалал 1, 2, ..., $n$ нь $a_{1}$, $a_{2}$, ..., $a_{n}$ гэж өөрчлөгдсөн байна.

Оролт

Эхний мөрөнд чатуудын тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоонууд $a_{1}$, $a_{2}$, ..., $a_{n}$-уудын бүртгэл өгөгдөх ба энд $a_{i}$ ($1 ≤ a_{i} ≤ n$) нь шинэ бүртгэл дэх $i$-дахь чатын хуучин байрлалыг илэрхийлнэ. Бүх $a_{i}$-ууд нь ялгаатай байна.

Гаралт

Баттай шинэ захиа агуулах чатуудын тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээнд, 2 болон 5-р чатууд нь 1-р чатын өмнө байрласан байх ба иймд эдгээр чатууд нь заавал шинэ захиа агуулах юм. Хэрэв зөвхөн 2 болон 5-р чатууд нь шинэ захианууд агуулсан бол 1, 3 болон 4-р чатууд нь магадгүй шинэ захиа агуулаагүй байна.

2-дахь жишээнд, чатуудын дараалал нь өөрчлөгдөөгүй тул ямар ч шинэ захиа байхгүй байна.

3-дахь жишээнд зөвхөн 1-р чат нь ямар ч шинэ захиа агуулаагүй байна.

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