Limits 1s, 512 MB

‘’True wisdom lies not in knowing all the answers, but in embracing the mystery of the unknown and allowing it to guide us towards new understandings.’’ - written by Artificial Intelligence.

Artificial intelligence (AI) has undoubtedly become increasingly powerful each day. Its ability to solve complex problems is one of the most remarkable advancements in recent times. Is it possible that one day humans will follow AI instructions without knowing what they are doing?

Imagine you are living in a world where AI is ruling. Every person follows AI instructions, and you are one of them.

In your imaginary world, there are NN portals, and each is numbered from 11 to NN. You can open any portal with some instructions given by artificial intelligence. In the beginning, all the portals are closed.

Each ith(1iN)i^{th} \: (1 \le i \le N) portal has a number written on it, denoted by CiC_i. if CiC_i is positive every time you are on the ithi^{th} portal, you will receive a reward of CiC_i coins, whereas if CiC_i is negative, you will be penalized and lose CiC_i coins.

Initially, you have 00 coins, and it is guaranteed that the instructions provided by the artificial intelligence will ensure that you always have a non-negative number of coins.

There are two types of instructions provided by artificial intelligence:

  1. GOTO ii: This instruction requires you to leave the current portal without closing it and open the ithi^{th} portal. Initially, you are not at any portal.

  2. PREVIOUS: This instruction instructs you to close the current portal and leave it. Then go to the portal opened exactly before it. If the AI instructs you to go previously, it is guaranteed that you previously came from another portal to the current portal.

You have been given QQ instructions to follow in order to collect coins. After following all the instructions, you need to determine the total number of coins you have obtained.


The first line of the input contains two positive integers NN and QQ (1N105;1Q106)(1 \le N \le 10^5; \: 1 \le Q \le 10^6), separated by a space — the number of portals and instructions, respectively.

The second line contains NN integers C1,C2,C3,..,CN(103Ci103)C_1, C_2, C_3,….., C_N \: (-10^3 \le C_i \le 10^3) — the number of coin in ithi^{th} portal.

The instructions will be given in the following QQ lines.

Each line will either contain "GOTO ii" (1iN)(1 \le i \le N) or "PREVIOUS" without quotation marks.


Output a single integer — indicating the total number of coins obtained after following all the instructions.


5 3
1 -3 4 0 9

At first, you open the 3rd3^{rd} portal and receive a reward of 44 coins. Currently you have 0+4=40+4 = 4 coins.

Then, you leave the 3rd3^{rd} portal without closing it. After that, you have to open the 2nd2^{nd} portal and pay a penalty of 33 coins. Currently you have 43=14-3 = 1 coins.

Lastly, you leave the 2nd2^{nd} portal and closing it. Then, you have to go to the portal opened exactly before it, which is the 3rd3^{rd} portal and receive 44 coins as reward. Currently you have 1+4=51+ 4= 5 coins.


Login to submit.


70% Solution Ratio
Billah_MasumEarliest, 6M ago
pathanFastest, 0.1s
emon.088977Lightest, 4.9 MB
Shovon_AhmedShortest, 407B
Toph uses cookies. By continuing you agree to our Cookie Policy.