#asaporo2c. [asaporo2_c]Paired Parentheses
[asaporo2_c]Paired Parentheses
Problem Statement
You are given two sequences and , both of length . The -th elements in and are and , respectively. Using these sequences, Snuke is doing the job of calculating the beauty of pairs of balanced sequences of parentheses (defined below) of length . The beauty of a pair is calculated as follows:
- Let .
- For each between and (inclusive), increment by if , and increment by otherwise.
- The beauty of is the final value of .
You will be given queries. Process them in order. In the -th query, update the value of to , and the value of to . Then, find the maximum possible beauty of a pair of balanced sequences of parentheses.
In this problem, only the sequences below are defined to be balanced sequences of parentheses.
- An empty string
- The concatenation of
(
, ,)
in this order, where is a balanced sequence of parentheses - The concatenation of , in this order, where and are balanced sequences of parentheses
Constraints
- All input values are integers.
Partial Scores
- In the test set worth points, and .
- In the test set worth points, .
Input
Input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain the response to the -th query.
Sample Input 1
Sample Output 1
- The first query updates and to . The maximum possible beauty is for
()()
,()()
. - The second query updates and to . The maximum possible beauty is for
()()
,(())
.