004 - Max_quantity

問題

数列$A$が与えられる。以下のクエリを処理せよ。

クエリ１

1 $x$ $k$

$A$の$x$番目の値を$k$に変更する。

クエリ２

2 $l$ $r$

($A_l$,$A_{l+1}$,...$A_r$)の中に存在する最大値とその個数を出力せよ。

入力

$N$
$A_1$ $A_2$ ... $A_N$
$Q$
$Query1$
$Query2$
 :
$QueryQ$

出力

クエリ2の結果を改行区切りで出力せよ。

制約

$1 \leq N,Q \leq 10^6$

$0 \leq A_i \leq 10^9(1 \leq i \leq N)$

$0 \leq k \leq 10^9$

$1 \leq l < r \leq N$

$1 \leq x \leq N$

クエリ2は必ず存在する

入力はすべて整数

入出力

入力例１

10
3 1 4 1 5 9 2 6 5 3
5
2 1 4 
2 1 10
1 2 4
1 4 4
2 2 4

出力例１

4 1
9 1
4 3

1,2つめのクエリはそれぞれ
$max(3,1,4,1) = 4$,$4$の個数は$1$
$max(3,1,4,1,5,9,2,6,5,3) = 9$,$9$の個数は$1$
となります。
3,4つめのクエリ後は$A$は$(3,4,4,4,5,9,2,6,5,3)$となります。
5つめのクエリは$max(4,4,4) = 4$,$4$の個数は$3$となります。

入力例２

10
7 2 9 3 7 4 9 8 3 7
10
1 7 2
2 9 10
1 5 9
1 2 4
1 4 7
1 1 2
1 3 5
1 7 9
2 2 10    
2 2 10    

出力例２

7 1
9 2
9 2