설거지

베시와 엘시는 농부 존이 설거지하는 일을 돕고 있다. 소에게는 엄지손가락이 없어서 생각보다 복잡한 작업이다. 두 소는 베시가 비누를 칠하고 엘시가 헹구기로 정했다. 베시에게는 $1$부터 $N$까지 번호가 붙은 더러운 접시 더미가 주어진다($1 \leq N \leq 10^5$). 엘시에게는 깨끗한 접시를 쌓을 빈 더미가 있다. 베시와 엘시 사이에는 비누칠한 더미를 놓는 조리대가 있다.

각 단계에서 다음 중 하나가 일어난다.

베시가 더러운 더미의 맨 위 접시를 가져와 비누를 칠한 뒤 조리대에 올린다. 비누칠한 접시를 올릴 때 베시는 (i) 비어 있지 않은 기존 비누칠 더미 위에 올리거나, (ii) 기존의 모든 비누칠 더미 오른쪽에 새 비누칠 더미를 만들어야 한다.

엘시가 가장 왼쪽 비누칠 더미의 맨 위 접시를 가져와 헹군 뒤 깨끗한 더미 위에 올린다.

목표는 깨끗한 더미에 접시가 번호 순서대로 쌓이는 것이다. 가장 작은 번호가 맨 아래, 가장 큰 번호가 맨 위에 와야 한다. 전체 더미로는 목표를 달성하지 못할 수 있으므로, 목표를 달성할 수 있는 입력 순서의 가장 긴 앞부분의 길이를 구하라.

첫 줄에 $N$이 주어진다. 다음 $N$개의 줄에는 베시 더미에 있는 접시의 순서가 주어지며, 첫 번째 수가 더미의 맨 위 접시이다.

소들이 설거지를 성공적으로 끝내서 깨끗한 더미의 접시가 올바른 순서로 놓일 수 있는, 입력 더미의 가장 긴 앞부분의 길이를 출력하라.