「Codeforces 1156E」Special Segments of Permutation
题目链接：Codeforces 1156E
你有一个长度为 $n$ 的排列 $p$，假如 $p_l + p_r = \max_{i = l} ^ r p_i$，那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。
数据范围：$3 \le n \le 2 \times 10 ^ 5$。
题目链接：Codeforces 1156E
你有一个长度为 $n$ 的排列 $p$，假如 $p_l + p_r = \max_{i = l} ^ r p_i$，那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。
数据范围：$3 \le n \le 2 \times 10 ^ 5$。
题目链接：LOJ 3052
距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力控制系统的一个芯片中。
「春节十二响」由 $n$ 个子程序构成，第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树，其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。
由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, \dots, S_k$，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当 $a$ 和 $b$ 在调用树上不是祖先-后代关系，$a$ 和 $b$ 可以被分配到同一个段中。
一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段大小的和不能超过系统的内存大小。
现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正确运行。即：最少需要多大的内存，才能通过先将内存分成若干个段，再把每个子程序分配到一个段中，使得每个段中分配的所有子程序之间不存在祖先-后代关系。
数据范围：$1 \le n \le 2 \times 10 ^ 5$，$1 \le M_i \le 10 ^ 9$。