Эмускальд подсел на Codeforces — теперь он постоянно обновляет главную страницу, чтобы не пропустить никаких изменений в списке прямого эфира. Ему нравится читать обсуждения (треды), каждое обсуждение состоит из нескольких сообщений.
Прямой эфир отображает список n различных обсуждений, упорядоченных по времени последнего сообщения в обсуждении. Когда в обсуждении публикуется очередное сообщение, оно перемещается на вершину списка. Никакие два сообщения в различных обсуждениях никогда не публикуются одновременно.
Эмускальд дочитал все свои открытые обсуждения. Теперь он обновляет главную страницу, надеясь найти еще немного новых сообщений. Обновив станицу, Эмускальд заметил, что новые обсуждения не появились в списке, а на i-м месте в списке стоит обсуждение, которое занимало ai-ое место до обновления. Эмускальд не хочет терять времени на перечитывание старых сообщений, поэтому он хочет открыть только обсуждения с новыми сообщениями.
Помогите Эмускальду узнать количество обсуждений, которые наверняка содержат новые сообщения. Обсуждение x наверняка содержит новое сообщение, если не существует такой последовательности публикаций новых сообщений, для которой выполняются оба следующих условия:
- обсуждение x не обновлено (в нем не опубликовано новое сообщение);
- порядок 1, 2, ..., n обсуждений в списке меняется на a1, a2, ..., an.
Примечание
В первом тесте обсуждения 2 и 5 поставлены перед обсуждением 1, значит, в этих обсуждениях должны быть новые сообщения. Обсуждения 1, 3 и 4 могут не содержать новых сообщений, если новые сообщения есть только в обсуждениях 2 и 5.
Во втором тесте может вообще не быть новых сообщений, потому что порядок обсуждений не изменился.
В третьем тесте только в обсуждении a4 может не быть новых сообщений.