Stairway to the Skyline

Stairway to the Skyline

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 512.0 MB

Description

Mike, a dreamer, recently visited a city called Wonderland, known for its towering skyscrapers. He wondered if he could rearrange a contiguous segment of buildings to form a "staircase" — a sequence where each building's height is at least as tall as the previous one.

Mike recorded the heights of n buildings in order as he walked through the city. He wants to find out if it is possible to select a single contiguous segment of at most k buildings and reorder that segment to create the staircase. The buildings are numbered from 1 to n.

Given the heights of the building, determine if there exists a segment of no more than k consecutive buildings that can be rearranged to form a staircase. If multiple such segments exist, output the leftmost smallest range. If it is not possible to form the staircase, output "NO". You can safely assume the the skycrapers does not form a staircase initially.

Format

Input

  • An integer n: the number of buildings.
  • An integer k: the maximum number of consecutive buildings Mike can reorder.
  • An array of n integers representing the heights of each building in sequence.

Constraints
\(2 <= n, k <= 10^5\)
\(1 <= h[i] <= 10^9\)

Output

  • If a suitable segment exists, output YES, followed by a new line indicating the smallest possible range l r
  • If no such segment exists, output NO.

Sample 1

Input

5 2
1 2 4 3 5

Output

YES
3 4

Sample 2

Input

5 2
1 4 2 3 5

Output

NO

Explanation

In the first test case of sample 1, you can select the segment from positions 3 to 4 (heights: 4, 3). By reordering these 2 elements, you can create the non-decreasing sequence: (3, 4).

In the second test case of sample 2, the smallest segment to reorder is from positions 2 to 4 (heights: 4, 2, 3), which requires reordering 3 elements, exceeding the limit of k, thus the output is "NO".

Brain Booster #7

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
8
Start at
2024-11-05 14:30
End at
2024-11-05 16:45
Duration
2.2 hour(s)
Host
Partic.
142