問題一覧 > 通常問題

No.2036 Max Middle

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 147
作問者 : milkcoffee / テスター : nok0 riano
お気に入りにしたユーザー ProblemId : 8254 / 自分の提出
問題文最終更新日: 2022-08-10 13:23:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 356 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A$ of length $N$. For $A$, $A_i \neq A_{i+1} \ (1 \leq i \leq N-1)$ holds.
You can perform the following operation on the integer sequence $A$.

  • Choose an integer $i \ (1 \leq i \leq N-2)$ such that $A_i< A_{i+1}$ and $A_{i+1}>A_{i+2}$. Then, replace $A_{i+1}$ with $\mathrm{min}(A_{i},A_{i+2})-1$.
At most how many times can you perform the operation?

Input

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

  • $3 \leq N \leq 2 \times 10^5$
  • $-10^9 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
  • $A_i \neq A_{i+1} \ (1 \leq i \leq N-1)$
  • All input values are integers.

    • Output

    Print the maximum number of times the operation can be performed, as an integer.

    Sample

    Sample 1
    Input
    4
2 4 3 -1
    Output
    2

    First, performing the operation with $i=1$ gives $A=(2,1,3,-1)$.
    Next, performing the operation with $i=2$ gives $A=(2,1,-2,-1)$.
    The operation has now been performed $2$ times. It is not possible to perform the operation more times than this.

    Sample 2
    Input
    3
100 -100 100
    Output
    0

    There are cases where the operation cannot be performed even $1$ time.

    Sample 3
    Input
    3
-1000000000 0 -1000000000
    Output
    1

    A value after the operation may be less than $-10^9$.

    Sample 4
    Input
    7
-5 -21 0 10 9 30 29
    Output
    5

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。