Stairway to the Skyline

Stairway to the Skyline

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".

Information

ID
1120
Difficulty
4
Category
(None)
Tags
(None)
# Submissions
160
Accepted
42
Accepted Ratio
26%
Uploaded By