B'Bob is playing a game of Spaceship Solitaire. The goal of this game is to build a spaceship. In order to do this, he first needs to accumulate enough resources for the construction. There are n types of resources, numbered 1 through n . Bob needs at least a_i pieces of the i -th resource to build the spaceship. The number a_i is called the goal for resource i . Each resource takes 1 turn to produce and in each turn only one resource can be produced. However, there are certain milestones that speed up production. Every milestone is a triple (s_j, t_j, u_j) , meaning that as soon as Bob has t_j units of the resource s_j , he receives one unit of the resource u_j for free, without him needing to spend a turn. It is possible that getting this free resource allows Bob to claim reward for another milestone. This way, he can obtain a large number of resources in a single turn. The game is constructed in such a way that there are never two milestones that have the same s_j and t_j , that is, the award for reaching t_j units of resource s_j is at most one additional resource. A bonus is never awarded for 0 of any resource, neither for reaching the goal a_i nor for going past the goal -- formally, for every milestone 0 < t_j < a_{s_j} . A bonus for reaching certain amount of a resource can be the resource itself, that is, s_j = u_j . Initially there are no milestones. You are to process q updates, each of which adds, removes or modifies a milestone. After every update, output the minimum number of turns needed to finish the game, that is, to accumulate at least a_i of i -th resource for each i in [1, n] . The first line contains a single integer n ( 1 <= q n <= q 2 cdot 10^5 ) -- the number of types of resources. The second line contains n space separated integers a_1, a_2, ... , a_n ( 1 <= q a_i <= q 10^'...