Santa has gone around the world and delivered to every country around the world on Christmas, except one: North Korea. Unsurprisingly, all the kids in North Korea have been naughty this year; except for Kim Jong Un and his ~N-1~ guards in his triangular hotel in Pyongyang.

Each of the ~N~ rooms (labeled ~1 \dots N~) in Kim's hotel has a fireplace for Santa to drop off presents. Each fireplace is either connected to the chimney or to exactly ~1~ fireplace above it via a pipe. Each pipe may take a different amount of time for Santa to cross.

Being the naughty kid genius leader he is, Kim is trying to capture Santa to steal all the toys distribute the wealth. Kim set up a grapple gun pointing up in each of the fireplaces, waiting to grab Santa as soon as he enters the chimney. The grapple gun's projectile will travel along the pipes until it reaches the chimney. Unfortunately, the Soviet era detection systems and wiring are quite out of date and thus take time to give the signal to each of the grapple guns. Specifically, the grapple gun at the ~i^{th}~ fireplace will fire ~D_i~ seconds after Santa has entered the chimney.

Thankfully, Kim has all his best technicians working on a solution now. Before Santa arrives, Kim's technicians will make ~C~ changes in the system that changes the delay of the grapple gun at the ~u^{th}~ fireplace to ~v~ seconds. Because of their outdated training, they might even make the problem worse by increasing the delay time.

Santa wants to find a path down that will allow him to deliver the greatest number of presents without getting caught with a grapple gun. Santa will instantly fly out of the hotel the moment a grapple gun at or below him fires. Help him find save Christmas by calculating the value after each change Kim's technicians make.

Note: It takes Santa zero time to deliver the presents. However, if Santa arrives at a fireplace just as the grapple gun fires, he will not be able to deliver the present.

Input Specification

The first line contains ~N~, the number of nodes (~1 \le N \le 10^5~).

Followed by ~N~ space separated integers indicating the delays on the grapple guns initially. The delays will always be a positive integer less than or equal to ~10^9~.

Followed by ~N~ lines containing a pair of integers, the (parent, time to cross in seconds). Having 0 for parent means it's connected to the chimney. The time to cross will be a positive integer no greater than ~10^9~.

The next line contains ~C~, the number of changes (~1 \le C \le 10^5~).

Followed by ~C~ lines containing a pair of integers, the fireplace changed (1 indexed, chimney does not have a grapple gun and will never be changed) and the new time.

Output Specification

After each change, print the answer on its own line.

Subtask	Marks	Additional Constraints
1	10%	~N \le 5, C \le 5~
2	15%	~N \le 100~, each grapple gun will receive at most ~1~ fix.
3	15%	~N \le 1\,000~, the delay on each grapple gun will never increase.
4	20%	The parent of the ~i^{th}~ fireplace will be ~i-1~.
5	40%	No additional constraints.

Sample Input

5
10 2 10 2 10
0 1
1 2
2 4
1 1
2 6
4
4 5
4 1
2 10
4 10

Sample Output

2
0
0
3

Sample Explanation

Before any changes, the most Santa could deliver is 1 present. After he delivers a present to fireplace #1, there wouldn't be enough time to deliver to any others. If he tried going to #4, he would get hooked in by the grapple gun as he arrives.

The first change opens a path for Santa to deliver to #4, allowing him to deliver 2 presents.

The second change makes the grapple gun at #4 fire very early, thus Santa could not even deliver a single present safely.

The third change delays the firing of #2 significantly, but Santa isn't even able to get to #1 before the grapple gun at #4 fires, so he still can't deliver any presents.

The fourth change delays the firing of #4 significantly, allowing Santa to go all the way to either #3 or #5 to deliver 3 presents.