जाँचें कि कोई ऐरे स्टैक-सॉर्टेबल है या नहीं
1 से n तक के संख्याओं को यादृच्छिक क्रम में एक ऐरे के रूप में दिया गया है। आपको यह जाँचना है कि दिया गया ऐरे स्टैक-सॉर्टेबल है या नहीं। ऐरे
A तभी स्टैक-सॉर्टेबल कहलाएगा जब एक सहायक स्टैक का उपयोग करके हम एक ऐसा ऐरे B प्राप्त कर सकें जो एल्गोरिथ्म के अंत तक बढ़ते क्रम (increasing order) में पूर्णतः सॉर्ट हो जाए। जिन ऑपरेशनों की अनुमति है, वे हैं:Aके पहले तत्व को हटाकर उसे स्टैक पर पुश करना।
- स्टैक के टॉप तत्व को हटाकर
Bके cuối में जोड़ना।
यदि अंत में
B बढ़ते क्रम में सॉर्ट हो जाए, तो A स्टैक-सॉर्टेबल है।इनपुट
इनपुट की पहली पंक्ति में एकल पूर्णांक
n (1 ≤ n ≤ ) दिया जाता है।अगली पंक्ति में
n अंतरालों से अलग किए गए पूर्णांक (1 ≤ ≤ n) होते हैं।आउटपुट
यदि
A स्टैक-सॉर्टेबल है तो प्रोग्राम को Yes प्रिंट करना चाहिए, अन्यथा No प्रिंट करना चाहिए।उदाहरण
इनपुट | आउटपुट |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
व्याख्या
A = [4, 1, 2, 3], S = [], B = []
- Operation 1:
A = [1, 2, 3],S = [4],B = []
- Operation 1:
A = [2, 3],S = [4, 1],B = []
- Operation 2:
A = [2, 3],S = [4],B = [1]
- Operation 1:
A = [3],S = [4, 2],B = [1]
- Operation 2:
A = [3],S = [4],B = [1, 2]
- Operation 1:
A = [],S = [4, 3],B = [1, 2]
- Operation 2:
A = [],S = [4],B = [1, 2, 3]
- Operation 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
- Operation 1:
A = [2, 1],S = [3],B = []
- Operation 1:
A = [1],S = [3, 2],B = []
- Operation 1:
A = [],S = [3, 2, 1],B = []
- Operation 2:
A = [],S = [3, 2],B = [1]
- Operation 2:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
- Operation 1:
A = [2, 3],S = [1],B = []
- Operation 2:
A = [2, 3],S = [],B = [1]
- Operation 1:
A = [3],S = [2],B = [1]
- Operation 2:
A = [3],S = [],B = [1, 2]
- Operation 1:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
It’s impossible to stack-sort the array [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB