루미 알고리즘

#1642다이아Under Supervision

PO 2026 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

In the state of Oceania, N citizens stand in a line, numbered from 1 to N. Citizen i has height p_i, and the heights form a permutation of the integers 1 to N.

The Party wants to appoint as few observers as possible to ensure that no citizen is ever out of sight. If a citizen is appointed as an observer, that person is considered supervised, and additionally all citizens that the observer can see also become supervised.

Two citizens can see each other if every person between them is shorter than both of them. Formally, if i < j then citizens i and j can see each other precisely when

max(p_{i+1}, p_{i+2}, …, p_{j-1}) < min(p_i, p_j).

The same rule naturally applies when j < i as well.

Your task is to find the minimum number of observers that the Party must appoint so that all N citizens are kept under supervision.

Input

The first line contains an integer N (1 ≤ N ≤ 3 · 10^5), the number of citizens.

The second line contains N integers p_1, p_2, …, p_N, a permutation of the integers 1 to N.

Output

Print a single integer: the minimum number of observers that the Party must appoint so that all citizens are kept under supervision.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
18N ≤ 15
212N ≤ 200
317N ≤ 1000
428N ≤ 3 · 10^5, the permutation is chosen uniformly at random. (Uniformly at random means that the probability that a given permutation of 1,2,…,N is chosen is 1/N!, i.e. the same probability for all permutations.)
535No additional constraints.

Explanation of Samples

In Sample 1 there is only one citizen, so one observer is needed.

In Sample 2 it suffices to appoint citizen 3 (with height 3) as an observer. They can see citizen 2 since they stand next to each other, and can also see citizen 1 since the only person between them (citizen 2, with height 1) is shorter than both (1 < min(3, 2) = 2). Thus all three citizens are kept under supervision.

In Sample 3 each citizen can only see those standing directly next to them. For example, citizen 1 (height 1) cannot see citizen 3 (height 3) since citizen 2 (height 2) between them is not shorter than both (2 ≥ 1). An optimal solution is to appoint citizens 2 and 4: citizen 2 supervises citizens 1, 2 and 3, while citizen 4 supervises citizens 3, 4 and 5.

예제

예제 1

입력
1
1
출력
1

예제 2

입력
3
2 1 3
출력
1

예제 3

입력
5
1 2 3 4 5
출력
2

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.