Chắc hẳn, các bạn đều từng nghe đến khái niệm dãy hình nón khi học thuật toán quy hoạch động.

Dãy ~a~ gồm ~n~ phần tử là dãy hình nón khi và chỉ khi tồn tại ~i~ (~1 \le i \le n~) sao cho ~a_1 \le a_2 \le ... \le a_i~ và ~a_i \ge a_{i + 1} \ge ... \ge a_n~.

Tất nhiên,duong3982 cũng thế và anh ấy rất hứng thú với dãy số này. Vì quá rảnh rỗi sinh nông nỗi, anh ấy quyết định cho bạn bài toán liên quan đến dãy số trên.

Cho mảng ~a~ gồm ~n~ phần tử. duong3982 muốn chia dãy thành các đoạn liên tiếp và sắp xếp lại sao cho chúng thỏa mãn dãy sau khi sắp xếp lại là một dãy hình nón.

Hỏi duong3982 cần chia thành ít nhất bao nhiêu đoạn để tạo thành một dãy hình nón?

INPUT

Dòng đầu tiên chứa ba số nguyên dương ~n~ (~1 \le n \le 50~).

Dòng tiếp theo gồm ~n~ số nguyên ~a_i~ (~0 \le a_i \le 10^5~).

OUTPUT

Số đoạn mà duong3982 cần phải chia.

SAMPLE INPUT 1

6
3 2 1 1 2 3

SAMPLE OUTPUT 1

2

SAMPLE INPUT 2

5
0 1 0 0 0

SAMPLE OUTPUT 2

1

Giải thích:

• Ở ví dụ 1: Đoạn 3 2 1 1 2 3 ta chia thành 3 2 1 | 1 2 3. Sau đó, ta sẽ sắp xếp thành 1 2 3 | 3 2 1.
• Ở ví dụ 2: Đoạn 0 1 0 0 0 được giữ nguyên do đã thỏa mãn điều kiện đề bài.

SUBTASKS