codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1272D.md (1458B)


      1 Source: https://codeforces.com/problemset/problem/1272/D
      2 
      3 D. Remove One Element
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ consisting of $n$ integers.
     22 
     23 You can remove at most one element from this array. Thus, the final length of the array is $n-1$ or $n$.
     24 
     25 Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.
     26 
     27 Recall that the contiguous subarray $a$ with indices from $l$ to $r$ is $a[l \dots r] = a_l, a_{l + 1}, \dots, a_r$. The subarray $a[l \dots r]$ is called strictly increasing if $a_l \lt a_{l+1} \lt \dots \lt a_r$.
     28 
     29 Input
     30 
     31 The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.
     32 
     33 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.
     34 
     35 Output
     36 
     37 Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array $a$ after removing at most one element.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5
     45 1 2 5 3 4
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 4
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 2
     58 1 2
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 7
     71 6 5 4 3 2 4 3
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 2
     78 ```
     79 
     80 Note
     81 
     82 In the first example, you can delete $a_3=5$. Then the resulting array will be equal to $[1, 2, 3, 4]$ and the length of its largest increasing subarray will be equal to $4$.