A7118. 求区间最大值（填空题）

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$。请你使用**分治递归**计算整个数组的最大值。

分治思想：把区间 $[l,r]$ 拆成左右两半 $[l,mid]$ 与 $[mid+1,r]$，分别递归求最大值，再合并答案。

### 具体例子
- 若 $a=[2,7,1,5]$，可拆成 $[2,7]$ 与 $[1,5]$：左半最大为 $7$，右半最大为 $5$，合并得到整体最大为 $7$。
- 若区间只有一个数（例如 $[l,l]$），该区间最大值就是这个数本身。

第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出一行一个整数，表示数组最大值。

## 数据范围
- $1\le n\le 2\times 10^5$
- $-10^9\le a_i\le 10^9$

## 样例解释
数组为
$$ a_1=2,\ a_2=7,\ a_3=1,\ a_4=9,\ a_5=3. $$
我们要求区间 $[1,5]$ 的最大值。

**第 $1$ 步：** 取
$$ mid=\left\lfloor\frac{1+5}{2}\right\rfloor=3, $$
把 $[1,5]$ 分成 $[1,3]$ 与 $[4,5]$。

---

### 计算左半区间 $[1,3]$ 的最大值
对区间 $[1,3]$，取
$$ mid=\left\lfloor\frac{1+3}{2}\right\rfloor=2, $$
拆成 $[1,2]$ 与 $[3,3]$。

- 对区间 $[1,2]$，取
$$ mid=\left\lfloor\frac{1+2}{2}\right\rfloor=1, $$
拆成 $[1,1]$ 与 $[2,2]$。
- $[1,1]$ 只有一个数，因此最大值为 $a_1=2$。
- $[2,2]$ 只有一个数，因此最大值为 $a_2=7$。
- 合并得到
$$ \max([1,2])=\max(2,7)=7. $$

- 对区间 $[3,3]$，只有一个数，因此最大值为 $a_3=1$。

合并得到
$$ \max([1,3])=\max(\max([1,2]),\max([3,3]))=\max(7,1)=7. $$

---

### 计算右半区间 $[4,5]$ 的最大值
对区间 $[4,5]$，取
$$ mid=\left\lfloor\frac{4+5}{2}\right\rfloor=4, $$
拆成 $[4,4]$ 与 $[5,5]$。
- $[4,4]$ 只有一个数，因此最大值为 $a_4=9$。
- $[5,5]$ 只有一个数，因此最大值为 $a_5=3$。

合并得到
$$ \max([4,5])=\max(9,3)=9. $$

---

### 最后合并得到整个区间 $[1,5]$ 的最大值
把左半与右半合并：
$$ \max([1,5])=\max(\max([1,3]),\max([4,5]))=\max(7,9)=9. $$
因此输出为 $9$。