Sort the Array · Interview Problem

Codeforces

Medium

Arrays

Sorting

Sort the Array

Determine whether an array can be sorted by reversing exactly one contiguous segment, and output that segment if possible.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given an array of integers. Your task is to check whether the array can be transformed into a nondecreasing array by reversing one contiguous subarray at most once.

If it is possible, output the left and right boundaries of such a segment (1-indexed). If the array is already sorted, any single-element segment is acceptable. If no such segment exists, report that it is impossible.

Notes

A nondecreasing array satisfies $a_1 \le a_2 \le \dots \le a_n$ .
Reversing a segment means taking a contiguous block and flipping its order.
The segment boundaries are inclusive.

Input Format

The first line contains an integer $n$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .

Output Format

If the array can be sorted by reversing one segment, print two integers $l$ and $r$ — the boundaries of the segment.
Otherwise, print -1.

Constraints

$1 \le n \le 10^5$
Integers in the array fit in 32-bit signed integer range
A linear-time or near-linear-time solution is expected

Hints

Compare the array with its sorted version to find the first and last mismatching positions.
After reversing that segment, verify that the whole array becomes nondecreasing.

Input Format

n — number of elements in the array.
a[1..n] — the array values.

Output Format

Print l r if reversing a[l..r] makes the array sorted.
Print -1 if it is impossible.

Constraints

$1 \le n \le 10^5$
Array values fit in 32-bit signed integers
Expected time complexity: $O(n \log n)$ or better

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 3 2 4 5

Output

2 3

Explanation

Reversing the segment [3, 2] gives [1, 2, 3, 4, 5], which is sorted.

Example 2

Input

4
1 2 3 4

Output

1 1

Explanation

The array is already sorted, so a length-1 segment is a valid answer.

Show 1 more example

Example 3

Input

4
4 3 2 1

Output

1 4

Explanation

Reversing the whole array makes it sorted.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress