Link Sub: http://www.spoj.com/PTIT/problems/P153SUMI/
Người Gửi: Funny
- Problem:
Cho dãy số có n phần tử gồm a[1], a[2], a[3], ..., a[n]. Và một thao tác biến đổi như sau, lấy phần tử cuối cùng của dãy số chuyển lên vị trí đầu tiên, ví dụ: a[1] , a[2], a[3] sẽ thành a[3], a[1], a[2].Yêu cầu: Với thao tác biến đổi như vậy thì dãy a[] có thể được chuyển thành một dãy không giảm sau một số thao tác hữu hạn nào đó không.
Input
Dòng đầu tiên là số nguyên n (1 <= n <= 10^5).
Dòng thứ hai chứa n số nguyên a[1], a[2], a[3], ..., a[n] (1 <= a[i] <= 10^5).
Output
In ra số thao tác cần thiết để biến đổi dãy số, hoặc in ra -1 nếu không thể biến đổi được dãy số ban đầu thỏa mãn yêu cầu.
Example:
In ra số thao tác cần thiết để biến đổi dãy số, hoặc in ra -1 nếu không thể biến đổi được dãy số ban đầu thỏa mãn yêu cầu.
Input
2
2 1
Output:
1
- Solution:
Chỉ có 2 trường hợp thỏa mãn đó là: - Chỉ có hai dãy không giảm và phần tử đầu của dãy 1 >= phần tử cuối dãy 2.
- Chỉ có 1 dãy không giảm.