All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Bob and Walls
Tag(s):

Easy

Problem
Editorial
Analytics

Bob the builder has constructed some walls of various length in a line. Now, he wants to count the total number of walls constructed and report that number to his boss. But the report that Bob made was wrong because he counted the total number of walls by standing on the leftmost side of the first wall. So he was only able to see some walls and not all because others were hidden behind. Can you predict the number of walls counted by Bob.

Input
First line contains T denoting the number of test cases.
First line of each test case contains N denoting the actual no of walls.
Second line of each test case contains N integers (A1...An) denoting the height of each walls.

Output
For each test case print a single integer denoting the total no of walls as counted by Bob each in a new line.

Constraints
T<=20
N<=100000
Ai<=10000

Problem Setter
Shikhar Kunal

SAMPLE INPUT
4
5
1 3 2 5 4
5
1 2 3 4 5
5
5 4 3 2 1
5
1 4 3 2 5
SAMPLE OUTPUT
3
5
1
3
Explanation

Sample 1: Bob will only be able to see the walls of length 1,3 and 5
Sample 2: Bob will be able to see all the walls
Sample 3: Bob will only be able to see the first wall
Sample 4: Bob will only be able to see the walls of length 1,4 and 5

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?