#KGSS. Maximum Sum

Maximum Sum

当前没有测试数据。

You are given a sequence A[1], A[2], ..., A[N] ( 0 ≤ A[i] ≤ 10^8 , 2 ≤ N ≤ 10^5 ). There are two types of operations and they are defined as follows:

Update:

This will be indicated in the input by a 'U' followed by space and then two integers i and x.

U i x, 1 ≤ i ≤ N, and x, 0 ≤ x ≤ 10^8.

This operation sets the value of A[i] to x.

Query:

This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.

Q x y, 1 ≤ x < y ≤ N.

You must find i and j such that x ≤ i, j ≤ y and i != j, such that the sum A[i]+A[j] is maximized. Print the sum A[i]+A[j].

Input

The first line of input consists of an integer N representing the length of the sequence. Next line consists of N space separated integers A[i]. Next line contains an integer Q, Q ≤ 10^5, representing the number of operations. Next Q lines contain the operations.

Output

Output the maximum sum mentioned above, in a separate line, for each Query.

Example

Input:
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5

Output:
7
9
11
12
Warning: large Input/Output data, be careful with certain languages
Submit solution! 
		<div id="ccontent">
		<!-- google_ad_section_start -->
hide comments

<script language="JavaScript">
<!--
$(document).ready(function(){
    $('.pager_link').bind('click', function(me){
            var href=$(me.currentTarget).attr('href');
	$('#ccontent').animate({opacity: 0.5},1);
            $.ajax({
                    type: "GET",
                    url: href+",ajax=1",
                    contentType: "application/x-www-form-urlencoded;charset=ISO-8859-2",
                    success: function(data){
                            $('#ccontent').html(data);
			$('#ccontent').animate({opacity: 1.0},1);
                    },
                    error: function(err){
                            alert('error');
                    }
            });
            return false;
    });
});
-->
</script>




		
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://d78nocSb.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/mortal_beast">mortal_beast</a>: 
							<span style="font-size: 10px; color: #666;">2021-06-06 15:17:15</span>
	<br>
			<p>Good for begineers</p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://HmZCM7gf.png">
	</td>
	<td class="comm comm_even">
		<a href="/users/rimuru_404">rimuru_404</a>: 
							<span style="font-size: 10px; color: #666;">2021-06-05 05:38:54</span>
	<br>
			<p>After some silly mistakes AC. Nice problem for segment tree beginners </p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://pMzZ5gR1.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/mukund007">mukund007</a>: 
							<span style="font-size: 10px; color: #666;">2021-05-30 08:43:03</span>
	<br>
			<p>Fenwick Tree go go</p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://6UrsLanD.png">
	</td>
	<td class="comm comm_even">
		<a href="/users/saurabh_kl">saurabh_kl</a>: 
							<span style="font-size: 10px; color: #666;">2021-02-11 21:05:39</span>
	<br>
			<p>Accepting Java solution, I don't know it gives TLE with Scanner or not but FastReader is okay</p>
			<b>Last edit: 2021-02-11 21:06:32</b>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://hIgvOrGo.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/kanisht09">kanisht09</a>: 
							<span style="font-size: 10px; color: #666;">2021-01-22 21:47:48</span>
	<br>
			<p>Solved it using segment trees 2 different ways</p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://jhbNMT1m.png">
	</td>
	<td class="comm comm_even">
		<a href="/users/saurav7192">saurav7192</a>: 
							<span style="font-size: 10px; color: #666;">2020-08-06 10:56:08</span>
	<br>
			<p>Aced finally..............................</p>
			<b>Last edit: 2020-08-06 12:30:50</b>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://6JNI9oeO.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/skj_helloworld">skj_helloworld</a>: 
							<span style="font-size: 10px; color: #666;">2020-08-04 12:34:34</span>
	<br>
			<p>accepted in one go</p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://9EZJX07Y.png">
	</td>
	<td class="comm comm_even">
		<a href="/users/chefpr7">chefpr7</a>: 
							<span style="font-size: 10px; color: #666;">2020-07-02 09:09:33</span>
	<br>
			<p>AC in One Go!! Nice practice problem for newbies!</p>
					</td>
</tr>
			
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://FqPk2abE.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/wargang">wargang</a>: 
							<span style="font-size: 10px; color: #666;">2020-07-01 13:25:12</span>
	<br>
			<p>very nice problem!!


</td> </tr></p> 
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://DV32nsJ2.png">
	</td>
	<td class="comm comm_even">
		<a href="/users/sarthak_19">sarthak_19</a>: 
							<span style="font-size: 10px; color: #666;">2020-06-29 06:21:49</span>
	<br>
			<p>AC in one GO!!!!!!!!


Good for Beginners

</td> </tr></p> 
		<!-- google_ad_section_end -->
		</div>
		<table width="100%">
            <tbody><tr>
            <td colspan="2" height="20px"></td>
    </tr>
    <form method="post" action="/comment/KGSS/add/"></form>
    <tr> <td style="" colspan="2">Leave a Comment</td> </tr>
    <tr>
            <td valign="top"></td>
            <td><textarea name="content" rows="3" class="form-control"></textarea></td>
    </tr>
    <tr>
            <td colspan="2" style=""><br>
                    <input type="submit" value="Publish" class="btn btn-default">
                    <input type="hidden" name="pcode" value="KGSS">
            </td>
    </tr>

Notes:
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our forum.
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to provide some useful links). 
    </tbody></table>

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2024 Hydro.ac
  4. Worker 0 in 68ms
  5. Hydro v4.12.0 Professional