Division into 3

AtCoder

IDarc180_d

Time3000ms

Memory256MB

Difficulty—

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$. Answer the following $Q$ queries. * The $i$\-th query: You are given integers $L_i$ and $R_i$. Solve the following problem for $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$. * Divide $B$ into three non-empty contiguous subsequences. For each contiguous subsequence, let us find the maximum value of its elements. Find the minimum possible sum of these maximum values. Here, the constraints of the problem force the length of $B$ to be at least $3$, so there is always at least one way to divide it into three non-empty contiguous subsequences. ## Constraints * $3 \leq N \leq 250000$ * $1 \leq Q \leq 250000$ * $1 \leq A_i \leq 10^8$ * $1 \leq L_i \leq R_i \leq N$ * $R_i - L_i \geq 2$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $A_2$ $\cdots$ $A_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$ [samples]

Samples

Input #1

7 5
4 3 1 1 4 5 2
1 7
2 4
3 5
1 5
4 7

Output #1

10
5
6
9
8

Let us explain the first query. We have $B=(4,3,1,1,4,5,2)$. If you divide it into $(4,3),(1,1),(4,5,2)$, the maximum values of the contiguous subsequences are $4,1,5$, respectively, and their sum is $10$. There is no way to make this sum smaller, so the answer to this query is $10$.

Input #2

10 15
8 3 8 10 1 5 3 1 6 4
4 6
2 5
6 9
8 10
2 9
4 10
1 5
1 8
1 3
4 8
1 10
2 10
6 10
2 6
2 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Division into 3",
    "description": {
      "content": "You are given an integer sequence $A=(A_1,A_2,\\cdots,A_N)$ of length $N$. Answer the following $Q$ queries. *   The $i$\\-th query: You are given integers $L_i$ and $R_i$. Solve the following problem ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc180_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence $A=(A_1,A_2,\\cdots,A_N)$ of length $N$. Answer the following $Q$ queries.\n\n*   The $i$\\-th query: You are given integers $L_i$ and $R_i$. Solve the following problem ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments