All Tracks Data Structures Arrays 1-D Problem

Long ATM Queue
Tag(s):

Data Structures, Easy, Greedy, approved

Problem
Editorial
Analytics

Due to the demonetization move, there is a long queue of people in front of ATMs. Due to withdrawal limit per person per day, people come in groups to withdraw money. Groups come one by one and line up behind the already present queue. The groups have a strange way of arranging themselves. In a particular group, the group members arrange themselves in increasing order of their height(not necessarily strictly increasing).

Swapy observes a long queue standing in front of the ATM near his house. Being a curious kid, he wants to count the total number of groups present in the queue waiting to withdraw money. Since groups are standing behind each other, one cannot differentiate between different groups and the exact count cannot be given. Can you tell him the minimum number of groups that can be observed in the queue?

Input format:

The first line of input contains one positive integer $$N$$. The second line contains $$N$$ space-separated integers $$H[i]$$ denoting the height of i-th person. Each group has group members standing in increasing order of their height.

Output format:

Print the minimum number of groups that are at least present in the queue?

Constraints:

  • $$1 ≤ N ≤ 1,000,000$$
  • $$1 ≤ H[ i ] ≤ 1,000,000$$
SAMPLE INPUT
4
1 2 3 4
SAMPLE OUTPUT
1
Explanation

In the second test case, Swapy observes all the people standing in increasing order of their height so at least one group is observed. Though it might be that 1st and 2nd came together and 3rd and 4th person came together but Swapy cannot differentiate.

In the third test case, he observes all the people standing in decreasing order of their height, hence it is certain that all of them came separately, so at least three groups are observed.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Darwinbox Digital Solutions Pvt.Ltd

Challenge Name

Darwinbox Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications