{\rtf1\ansi\ansicpg1252\cocoartf1504\cocoasubrtf830
{\fonttbl\f0\fmodern\fcharset0 CourierNewPSMT;\f1\fmodern\fcharset0 CourierNewPS-BoldMT;}
{\colortbl;\red255\green255\blue255;\red109\green109\blue109;\red255\green255\blue255;\red26\green26\blue26;
\red10\green82\blue135;\red0\green0\blue0;\red251\green0\blue129;\red0\green0\blue255;}
{\*\expandedcolortbl;;\cssrgb\c50196\c50196\c50196;\cssrgb\c100000\c100000\c100000;\cssrgb\c13333\c13333\c13333;
\cssrgb\c0\c40000\c60000;\cssrgb\c0\c0\c0;\cssrgb\c100000\c7843\c57647;\cssrgb\c0\c0\c100000;}
\paperw11900\paperh16840\margl1440\margr1440\vieww10800\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\sl264\partightenfactor0

\f0\fs24 \cf2 \cb3 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec2 #include <cstdio>\cf4 \strokec4 \
\cf2 \strokec2 #include <algorithm>\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0

\f1\b \cf5 \strokec5 using
\f0\b0 \cf4 \strokec4  
\f1\b \cf5 \strokec5 namespace
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 std;\cf4 \strokec4 \

\f1\b \cf5 \strokec5 const
\f0\b0 \cf4 \strokec4  
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 NMAX = 100000;\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0

\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 v[NMAX * 4 + 5];\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0

\f1\b \cf5 \strokec5 void
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 update(
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 nod, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 poz, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 val, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 st, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 dr)\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0
\cf6 \strokec6 \{\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (st == dr) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 v[nod] = val;\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf5 \strokec5 return
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 ;\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 mij = (st + dr) / 2;\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (poz <= mij) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 update(nod * 2, poz, val, st, mij);\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 else
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 update(nod * 2 + 1, poz, val, mij + 1, dr);\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 v[nod] = max(v[nod * 2], v[nod * 2 + 1]);\cf4 \strokec4 \
\cf6 \strokec6 \}\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0

\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 query(
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 nod, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 a, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 b, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 st, 
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 dr)\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0
\cf6 \strokec6 \{\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (a <= st && dr <= b) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf5 \strokec5 return
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 v[nod];\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 sol1 = 0, sol2 = 0;\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 mij = (st + dr) / 2;\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (a <= mij) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 sol1 = query(nod * 2, a, b, st, mij);\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (mij < b) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 sol2 = query(nod * 2 + 1, a, b, mij + 1, dr);\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 return
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 max(sol1, sol2);\cf4 \strokec4 \
\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\
\pard\pardeftab720\sl264\partightenfactor0

\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 main()\cf4 \strokec4 \
\pard\pardeftab720\sl264\partightenfactor0
\cf6 \strokec6 \{\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 n, m;\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf7 \strokec7 freopen
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "arbint.in"\cf6 \strokec6 , \cf8 \strokec8 "r"\cf6 \strokec6 , stdin);\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf7 \strokec7 freopen
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "arbint.out"\cf6 \strokec6 , \cf8 \strokec8 "w"\cf6 \strokec6 , stdout);\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf7 \strokec7 scanf
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "%d%d"\cf6 \strokec6 , &n, &m);\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 for
\f0\b0 \cf6 \strokec6 (
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 i = 1; i <= n; ++i) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 val;\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf7 \strokec7 scanf
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "%d"\cf6 \strokec6 , &val);\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 update(1, i, val, 1, n);\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 for
\f0\b0 \cf6 \strokec6 (
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 q = 0; q < m; ++q) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf2 \strokec2 int
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 t, a, b;\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf7 \strokec7 scanf
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "%d%d%d"\cf6 \strokec6 , &t, &a, &b);\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf5 \strokec5 if
\f0\b0 \cf6 \strokec6 (t == 1) \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\'a0\'a0\cf6 \strokec6 update(1, a, b, 1, n);\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0\'a0\'a0
\f1\b \cf5 \strokec5 else
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 \{\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\'a0\'a0
\f1\b \cf7 \strokec7 printf
\f0\b0 \cf6 \strokec6 (\cf8 \strokec8 "%d\\n"\cf6 \strokec6 , query(1, a, b, 1, n));\cf4 \strokec4 \
\'a0\'a0\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0\cf6 \strokec6 \}\cf4 \strokec4 \
\'a0\'a0
\f1\b \cf5 \strokec5 return
\f0\b0 \cf4 \strokec4  \cf6 \strokec6 0;\cf4 \strokec4 \
\cf6 \strokec6 \}\cf4 \strokec4 \
}