All Tracks Data Structures Stacks Basics of Stacks Problem

Monk and Philosopher's Stone
Tag(s):

Data Structures, Easy, Stack, approved, recruit

Problem
Editorial
Analytics

Harry Potter wants to get the Philosopher's stone to protect it from Snape. Monk being the guard of Philosopher's Stone is very greedy and has a special bag, into which he can add one gold coin at a time or can remove the last gold coin he added. Monk will sleep, once he will have the enough number of gold coins worth amount $$X$$. To help Harry, Dumbledore has given a same kind of bag to Harry (as of Monk) with $$N$$ gold coins each having worth $$A[ i ]$$ where i range from $$ 1 \le i \le N$$.

enter image description here

Dumbledore also gave him a set of instructions which contains two types of strings:
1) "Harry" (without quotes): It means Harry will remove $$i^{th}$$ coin from his bag and throw it towards Monk and Monk will add it in his bag, where $$i$$ will start from $$1$$ and go up to $$N$$.
2) "Remove" (without quotes): it means Monk will remove the last coin he added in his bag.
Once the worth of the coins in Monk's bag becomes equal to $$X$$, Monk will go to sleep. In order to report Dumbledore, Harry wants to know the number of coins in Monk's bag, the first time their worth becomes equal to $$X$$.

Help Harry for the same and print the required number of coins. If the required condition doesn't occur print "-1" (without quotes).

Input:
The first line will consists of one integer $$N$$ denoting the number of gold coins in Harry's Bag.
Second line contains $$N$$ space separated integers, denoting the worth of gold coins.
Third line contains 2 space separated integers $$Q$$ and $$X$$, denoting the number of instructions and the value of $$X$$ respectively.
In next $$Q$$ lines, each line contains one string either "Harry" (without quotes) or "Remove" (without quotes).

Output:
In one line, print the the number of coins in the Monk's bag, the first time their worth becomes equal to $$X$$.

Constraints:
$$1 \le N \le 10^4$$
$$1 \le A[ i ] \le 10^4$$
$$1 \le Q \le 10^5$$
$$1 \le X \le 10^7$$

SAMPLE INPUT
4
3 1 1 4
6 7
Harry
Harry
Harry
Remove
Remove
Harry
SAMPLE OUTPUT
2
Explanation

Initailly, set of instructions contains "Harry", then Harry will throw $$1^{st}$$ coin to Monk which is of worth $$3$$ . Similarly Monk will have $$2^{nd}$$ and $$3^{rd}$$ gold coin in its bag, both having worth $$1$$.

Now set contains "Remove" $$2$$ times, which means Monk will remove $$3^{rd}$$ and $$2^{nd}$$ coin, both having worth 1.

Now Harry will throw $$4^{th}$$ coin towards Monk having worth 4. Now the Monk's bag contains 2 coins with worth 3 and 4, which is equal to worth 7.

So the answer is 2.

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++, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Stacks & Queues)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications