Subtask 1 : ~(3 \leq n \leq 10 ^ 3)~

Ta xét mọi vị trí ~x \space (1 < x < n)~ và giả sử rằng ~a_x~ là đỉnh núi,ta có mảng ~b~ là các giá trị của mảng ~a~ sau khi thực hiện thao tác cộng 1 để ~a~ là ngọn núi ~a_x~ là đỉnh núi,để xây dựng mảng b thì nó cũng là một việc rất đơn giản.

Đầu tiên ta gán ~b_1 = a_1~,~b_n = a_n~,duyệt từ ~2\rightarrow x~ và gán ~b_i = max(b_{i - 1} + 1,a_i)~,duyệt từ ~n - 1 \rightarrow x~ và gán ~b_i = max(b_{i + 1} + 1,a_i)~.Ta hiểu đơn giản rằng ~a_i~ cần phỉa lớn hơn giá trị trước nó ít hơn một đơn vị để là một ngọn núi 1

Sau cùng số lần cần cộng 1 để xây ngọn núi khi ~a_x~ là đỉnh núi là $$\sum\limits_{i = 1} ^ {n} (b_i - a_i)$$

Mỗi lần ~x~ thay đổi ta cần tính lại đáp án trong O(n)

ĐPT : ~O(n ^ 2)~

Subtask 2 : ~(3 \leq n \leq 10 ^ 5)~

Gọi mảng ~pref~ là giá trị mảng a sau khi cộng 1 để ~a_{i - 1} < a_i (1 < i \leq n)~

Goị mảng ~suff~ là giá trị mảng a sau khi cộng 1 để ~a_{i - 1} > a_i (1 < i \leq n)~

Gọi mảng ~prefSum~ với $$prefSum_i = \sum\limits_{j = 1} ^ {i} (pref_j - a_j)$$

Gọi mảng ~suffSum~ với $$suffSum_i = \sum\limits_{j = i} ^ {n} (suff_j - a_j)$$

Cách tính mảng ~pref~ và ~suff~ cũng gần như tương tự với cách tính mảng ~b~ ở Subtask1

Còn để tính mảng ~prefSum~ và ~suffSum~ ta có thể áp dụng kiến thức mảng cộng dồn

Như vậy ta có thể xét mọi vị trí ~x \space (1 < x < n)~ nhưng lần này ta có thể lấy đáp án trong ~O(1)~

Số lần cần cộng 1 để xây ngọn núi khi ~a_x~ là đỉnh núi là $$prefSum_{x - 1} + suffSum_{x + 1} + max(pref_{x - 1} + 1,suff_{x + 1} + 1,a_x) - a_x$$

ĐPT : ~O(n)~