Problem 1E. 最小化网络并发线程分配

时间限制：1s

空间限制：64MB

题目背景

在网络通信中，存在多种并发网络任务，如资源请求和文件上传。这些任务的执行方式有些是线性或队列式的，而更多是并发执行的，需要服务器进行统一调度。对于多并发网络任务，可以通过多线程处理来提高处理速度。然而，计算资源和网络线程数都是有限的，因此需要找到一种方式来最小化分配给某项并发任务的线程数量。

题目描述

假设有 \(n\)个网络并发任务需要同时开始执行，每个任务都一个权重值，已知一个整数数组\(weights\)表示每个任务的权重值。

你可以为每个网络任务分配一个 整数数字，用来表示分配的网络线程数，且每个任务至少分配\(1\)个网络线程。

由于某种限制，要求 相邻 的两个任务的权值，权重更高的任务必须分配更多的线程（而对于相同权值两个的相邻任务，线程数没有限制）。

请你计算并输出一个整数，表示最小网络并发线程的分配数量。

输入格式

第一行一个整数 \(n\)，第二行是一个长度为\(n\)的整数数字\(weights\)

输出格式

一个整数，表示最小网络并发线程的分配数量，这种方式下，所有任务的线程之和最小。

样例输入1

3
1 0 2

样例输出1

5

样例1解释

最小化分配方式为：2 1 2

样例输入 2

6
1 2 2 2 2 1

样例输出 2

8

样例2解释

由于相同权重的线程分配并没有限制，最小化分配方式为：1 2 1 1 2 1

数据范围及限制

对于 \(100\%\) 的数据，\(1\le n\le 5\times10^4,weights[i]\in[1,100]\)