#P2145. 2024.9.29-ZJTD-第1题-小塔的木板

2024.9.29-ZJTD-第1题-小塔的木板

题目内容

小塔有nn个插在数轴上的木板，其中第ii块木板高度为aa，相邻木板之间的宽度为11，木板本身的宽度忽略不计。 现在小塔要使用这nn个木板来接雨水，他想知道如果他可以提前调整这些木板的排列顺序，那么最多可以接多少雨水?

输入描述

第一行输入一个整数 nn（2≤n≤2×1052≤n≤2×10^5）代表数组中的元素数量。

第二行输入nn个整数a1,a2,...,an(1≤ai≤109)a_1,a_2,...,a_n(1≤a_i≤10^9)表示每块木板的高度。

输出描述

在一行上输出一个整数，代表在任意排列所有木板后，可以接到雨水的最大量。

样例1

输入

4
1 3 4 5

输出

12

说明

p1

知识点:*****

查看知识点以及同类型题目

Statistics