flappybird Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

flappybird.html

Problem Description

A fire has broken out in a large tower with N floors, and there is a person stuck at each floor trying to get out. Feeling his internal sense of justice raging, Rar the Cat took to his helicopter and flew up to the top of the tower to attempt to save the people in the tower. When he got to the top of the tower, he found an empty lift shaft that was blown out by the fire. Peering into the lift shaft, he found that everyone was still busy playing Flappy Bird!

Wait what... a high score of 145? How could this be? How could anyone beat the mighty Rar the Cat? Fury raged inside Rar the Cat. Conflicted between the urge for revenge and the rivalry between his Flappy Bird foes, he comes out with a new plan. To save the people in the building, Rar the Cat will throw lift cars down the lift shaft to pick the people up. Since there is no electricity, the lift cars can only go downwards from floor N to the ground floor, where the people are supposed to get to. To execute his brilliant revenge plan, a lift car can only pick up a person at a certain floor if all the people currently in the lift car has a Flappy Bird high score higher than the person currently entering it.

Given a list of the Flappy Bird high scores of each of the people on each floor, find out the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.

Input

The first line of input will contain one integer, N.
The second line of input will contain N integers, with the ith integer representing the Flappy Bird high score of the person on floor i.

Output

Your output should contain one integer, the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.

Limits

All Flappy Bird high scores will be less than 2³¹-1.
Subtask 1 (14%): 1 ≤ N ≤ 10. In addition, all Flappy Bird high scores will be less than or equal to 10.
Subtask 2 (28%): 1 ≤ N ≤ 1000.
Subtask 3 (58%): 1 ≤ N ≤ 1000000.
Subtask 4 (0%): As per sample testcases.

Sample Input 1

5
1 2 3 3 5

Sample Output 1

Sample Input 2

5
5 4 2 5 1

Sample Output 2

Subtasks and Limits

Subtask	Score	#TC	Time	Memory	Scoring
1	14	20	1s	32MB	Minimum
2	28	40	1s	32MB	Minimum
3	58	60	1s	32MB	Minimum
4	0	2	1s	32MB	Minimum

Judge Compile Command

g++-7 ans.cpp -o flappybird -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512