Courses

동적 프로그래밍

GWP(최대 증가 하위 시퀀스)

Module: GWP(최대 증가 하위 시퀀스)

Problem

6 /6

카피바라. 케이블카

Problem

<사업부> 최근에 숲에 있었던 Vasya는 나무 위에 케이블카를 만들기로 결정했습니다. 그는 도로가 가능한 한 길기를 원하지만 숲의 나무 높이를 잘 기억하지 못합니다. 다행스럽게도 그는 모든 나무의 높이를 정확히 기억하고 있다고 확신하지만 그중 하나는 예외입니다.

<사업부>
숲은 일렬로 배열된 n개의 나무로 구성되어 있으며 왼쪽에서 오른쪽으로 1부터 n까지의 번호가 매겨져 있는 것으로 알려져 있습니다. Vasya에 따르면 i번째 트리의 높이는 h_i입니다. 길이가 k인 케이블카는 k(1 <= k <= n)개의 나무 i₁, i₂, . . . , i_k (i₁ < i₂ k) 높이가 증가한다는 것, 즉 h_i1 < h_i2 < . . . < h_ik.

<사업부> Petya도 숲에 있었고 그는 Vasya가 정확히 어디에서 잘못되었는지 추측했습니다. 그의 i번째 추측은 숫자 a_i 및 b_i 로 주어집니다. Petya의 의견으로는 나무의 높이

<사업부> 숫자 a_i 는 실제로 b_i 와 같습니다. Petya의 가정은 서로 독립적입니다.

<사업부>
귀하의 임무는 Petya의 각 추측에 대해 이러한 나무를 기반으로 건설할 수 있는 케이블카의 최대 길이를 찾는 것입니다.

<사업부> 이 문제의 틀 내에서 Vasya는 지원하는 나무의 수를 도로 길이로 간주합니다.

<사업부> 입력 데이터 형식

<사업부> 입력의 첫 번째 줄에는 두 개의 숫자 n과 m(1 <= n, m <= 400 000)이 포함됩니다. 숲의 나무 수와 Petya의 추측 수.

<사업부> 다음 줄에는 n 정수 h_i (1 <= h_i <= 10⁹ ) — Vasya의 제안에 따른 나무의 높이.

<사업부>
다음 m행 각각에는 두 개의 정수 a_i 및 b_i(1 <= a_i <= n, 1 <= b_i <= 10⁹ ).

<사업부>
출력 형식 <사업부> 각 Petya의 추측에 대해 별도의 줄에 하나의 숫자를 인쇄하십시오. 케이블카의 최대 길이.

<몸> <사업부> 참고 <사업부> 첫 번째 예를 살펴보겠습니다. Petya의 첫 번째 가정은 Vasya의 가정과 일치합니다. <사업부> 그의 두 번째 가정에 따르면 나무의 높이는 (4, 2, 3, 4)이고 세 번째는 (1, 2, 3, 3)이고 네 번째 가정에 따르면 — (1, 2, 3, 5).

time 3000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking