[CSP-X2023 山东] 赚钱

Luogu

IDLGB4100

Time1000ms

Memory512MB

DifficultyP2

2023山东CSP-X 小学组

小 A 很喜欢旅游，他的国家共有 $n$ 个城市，编号依次为 $1$ 到 $n$，这个暑假小 A 打算从 $1$ 号城市开始按编号从小到大依次旅游完所有的城市，最后达到 $n$ 号城市，而且他不走回头路，每个城市只走一次。小 A 很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是每个城市的价格却不完全一样（在同一个城市买入和卖出一个小熊纪念品的价格相同），于是小 A 打算从经过的某一个城市 $x$ 买一个纪念品，然后在后面经过的某个城市 $y$ 卖掉，从而赚取其中的差价。**但是他必须在某个城市买 $1$ 次，而且只能买 $1$ 个，并且一定要在后面的某个城市卖掉（不能在同一个城市先买入后再卖出）**，因为他家里已经有很多小熊纪念品了。如，$2$ 号城市的纪念品价格是 $10$ 元，$6$ 号城市的纪念品是 $8$ 元，$10$ 号城市的纪念品是 $18$ 元，假设小 A 在 $2$ 号城市花 $10$ 元钱买了一个纪念品，如果在 $6$ 号城市卖掉他就亏了 $2$ 元（赚 $-2$ 元），如果在 $10$ 号城市卖，他就会赚 $8$ 元。小 A 希望赚的钱越多越好。问：小 A 最多能赚多少钱（当然也有可能亏钱）？ ## Input 第一行一个整数 $n$，表示城市的个数。第二行，$n$ 个用一个空格隔开的正整数，$a_1,a_2,\ldots,a_n$，依次表示小 A 要经过的城市的纪念品的价格。 ## Output 输出一个整数，表示小 A 能赚到钱的最大值。 [samples] ## Note 对于 $30\%$ 的数据：$n\le 1000$。对于 $100\%$ 的数据：$2\le n\le 2\times 10^5$，$0\lt a_i\le 2\times 10^9$。

Samples

Input #1

5
2 1 6 8 4

Output #1

Input #2

6
10 8 7 5 3 1

Output #2

-1

API Response (JSON)

{
  "problem": {
    "name": "[CSP-X2023 山东] 赚钱",
    "description": {
      "content": "小 A 很喜欢旅游，他的国家共有 $n$ 个城市，编号依次为 $1$ 到 $n$，这个暑假小 A 打算从 $1$ 号城市开始按编号从小到大依次旅游完所有的城市，最后达到 $n$ 号城市，而且他不走回头路，每个城市只走一次。 小 A 很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是每个城市的价格却不完全一样（在同一个城市买入和卖出一个小熊纪念品的价格相同），于是小 A 打算",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4100"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 很喜欢旅游，他的国家共有 $n$ 个城市，编号依次为 $1$ 到 $n$，这个暑假小 A 打算从 $1$ 号城市开始按编号从小到大依次旅游完所有的城市，最后达到 $n$ 号城市，而且他不走回头路，每个城市只走一次。\n\n小 A 很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是每个城市的价格却不完全一样（在同一个城市买入和卖出一个小熊纪念品的价格相同），于是小 A 打算...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments