CSES - Pyramid Array | Mảng hình "kim"

Xem PDF
Tác giả:
letangphuquy
Dạng bài
Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho trước một mảng gồm \(n\) số nguyên phân biệt. Tại mỗi lượt, bạn có thể đảo vị trí của hai phần tử kề nhau.

Bạn muốn biến đổi mảng này thành dạng kim tự tháp. Nghĩa là mảng kết quả đầu tiên phải tăng dần, và sau đó giảm dần. Cho phép mảng cuối cùng chỉ tăng hoặc chỉ giảm.

Số lượng lượt đi tối thiểu là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên chứa \(n\): kích thước của mảng.
  • Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(x_1, x_2, \dots, x_n\): nội dung của mảng.

Output

  • In một số nguyên: số lượng nước đi tối thiểu.

Constraints

  • \(1 \leq n \leq 2 \cdot 10^5\)
  • \(1 \leq x_i \leq 10^9\)

Example

Sample input:

4
2 1 5 3

Sample output:
1

Note

Bạn có thể đổi chỗ hai phần tử đầu tiên, tạo nên mảng hình "kim" \([1,2,5,3]\)

Bình luận


  • 0
    nguyen_ducminh    2:18 a.m. 16 Tháng 9, 2023

    CSES - Pyramid Array | Mảng kim tự tháp

    Cho một mảng gồm \(n\) số nguyên phân biệt. Tại mỗi lượt, bạn có thể tráo vị trí của hai số kề nhau.

    Bạn phải biến đổi mảng ban đầu thành mảng kim tự tháp. Tức mảng kết quả đầu tiên phải tăng dần và sau đó giảm dần. Mảng kết quả chỉ tăng hoặc chỉ giảm cũng được chấp nhận.

    Số lượt đi cần thiết tối thiểu là bao nhiêu?

    Input

    • Dòng đầu tiên gồm số nguyên \(n\) (\(1 \leq n \leq 2\times10^5\)) - kích cỡ của mảng.
    • Dòng tiếp theo gồm \(n\) số nguyên \(x_1, x_2, ..., x_n\) (\(1 \leq x_i \leq 10^9\)) mô tả mảng.

    Output

    • In ra một số nguyên - số lượt đi cần thiết tối thiểu.

    Test 1

    Input 
    4
2 1 5 3
    Output 
    1
    Note

    Bạn có thể tráo hai phần tử đầu tiên và được mảng kết quả là \([1,2,5,3]\).