[Here](https://codeforces.me/contestInvitation/c9f73b6b05a07d2c184e732ba6641fa16c328e13) is the contest link.↵
↵
#### [A. The Ticket Booth](https://codeforces.me/gym/594077/problem/A)↵
↵
<spoiler summary = "Solution">↵
Simply put, the problem is asking us to represent $S$, as a summation of numbers from the set ${1, 2, 3, … ,n }$.↵
↵
Obviously there are many ways to do that, for example one might use $1$ $S$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.↵
↵
Since we have all the numbers from $1$ to $n$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $S$, until we get the sum of the selected elements equal to $S$. This ensures that we use the fewest possible numbers.↵
↵
This process can easily be represented by a ceil division of $S$ by $n$.↵
↵
because $⌈S/n⌉$ tells us how many times we would need to add the largest possible number (which is $n$) to reach or exceed $S$.↵
↵
Time complexity: $O(1)$.↵
Space complexity: $O(1)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n,S = map(int, input().split())↵
↵
print((S + n - 1) // n) ↵
```↵
</spoiler>↵
↵
↵
#### [B. Nafargi's Binary Reduction Game](https://codeforces.me/gym/594077/problem/B)↵
↵
<spoiler summary = "Solution">↵
The problem involves removing adjacent `01` or `10` pairs from a binary string until no more moves are possible. The goal is to find the minimum possible remaining length of the string.↵
↵
Stack-Based Solution:↵
Traverse the binary string while maintaining a stack.↵
If the stack is non-empty and the current character forms a removable pair (01 or 10) with the top of the stack, pop the stack.↵
Otherwise, push the current character onto the stack.↵
The size of the stack at the end represents the minimum remaining length.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input().strip())↵
s = input().strip()↵
stack = []↵
for char in s:↵
if stack and stack[-1] != char:↵
stack.pop() # Remove 01 or 10 pair↵
else:↵
stack.append(char) # Push character if no pair found↵
print(len(stack))↵
```↵
</spoiler>↵
↵
↵
#### [C. Permutation Minimization](https://codeforces.me/gym/594077/problem/C)↵
↵
<spoiler summary = "Solution">↵
<p>↵
We need the <b>deque</b> data structure to solve this problem. We iterate the given permutation starting from the first element and we append to the left of our <b>deque</b> either if it is empty or the element at the <b>0-th</b> index of our <b>deque</b> is larger than the current element we are about to add to our <b>deque</b>. Otherwise we append to the end of our <b>deque</b> because appending a larger number than what we currently have at the <b>0-th</b> index of our <b>deque</b> will definitly make our final answer <b>lexicographically larger</b>.↵
</p>↵
↵
<spoiler summary = "Time and space complexities">↵
<ul>↵
<li> <b> Time Complexity: O(n) </b> </li>↵
<li> <b> Space Complexity: O(n) </b> </li>↵
</ul>↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```↵
from collections import deque↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
ans = deque()↵
for num in arr:↵
if ans and num < ans[0]:↵
ans.appendleft(num)↵
else:↵
ans.append(num)↵
↵
print(*ans)↵
```↵
</spoiler>↵
↵
↵
#### [D. Meklit's Chat Screen](https://codeforces.me/gym/594077/problem/D)↵
↵
<spoiler summary="Hint 1">↵
- Think of a **queue** (FIFO structure) to store the most recent `k` unique chats.↵
- Use a **set** to quickly check if a friend's chat is already on the screen.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When a new chat arrives and the screen is full, **remove the oldest chat** before adding the new one.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The problem requires maintaining the most recent `k` unique chat messages in order. ↵
Key observations: ↵
1. If a friend sends multiple messages, only the first occurrence matters. ↵
2. If the chat screen is full (`k` elements), the oldest message is removed when a new unique message arrives. ↵
↵
### Approach:↵
- Use a **deque** (`chat_screen`) to store recent unique chats while maintaining order. ↵
- Use a **set** (`seen`) to track which friends are currently displayed. ↵
- Process each message: ↵
- If it's already in `seen`, ignore it.↵
- Otherwise: ↵
- If `chat_screen` is full, remove the **oldest** chat (last element). ↵
- Add the new chat to the **front** of `chat_screen` and update `seen`. ↵
- Print the final chat list. ↵
↵
This method ensures an **O(n) time complexity**, which is efficient for large inputs. ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
from collections import deque↵
↵
def chat_screen(n, k, messages):↵
chat_screen = deque()↵
seen = set()↵
↵
for id_i in messages:↵
if id_i not in seen:↵
if len(chat_screen) == k:↵
removed = chat_screen.pop()↵
seen.remove(removed)↵
↵
chat_screen.appendleft(id_i)↵
seen.add(id_i)↵
↵
print(len(chat_screen))↵
print(*chat_screen)↵
↵
n, k = map(int, input().split())↵
messages = list(map(int, input().split()))↵
chat_screen(n, k, messages)↵
↵
``` ↵
</spoiler>↵
↵
↵
#### [E. Minimum Subsequence](https://codeforces.me/gym/594077/problem/E)↵
↵
<spoiler summary="Hint 1">↵
- Think of maintaining **two lists** to track subsequences ending in `0` and `1`.↵
- A **greedy approach** helps in assigning characters to subsequences optimally.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
- If a `1` appears, assign it to a subsequence that previously ended in `0`.↵
- If a `0` appears, assign it to a subsequence that previously ended in `1`.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The problem requires dividing the binary string into the **minimum number** of subsequences ↵
such that each follows an alternating `0-1` or `1-0` pattern.↵
↵
1. Each character belongs to exactly **one** subsequence.↵
2. If a `1` appears, it should ideally continue a subsequence ending in `0`, and vice versa.↵
3. We can efficiently track and assign subsequences using two lists:↵
- `zero` → Stores subsequences ending in `0`.↵
- `one` → Stores subsequences ending in `1`.↵
↵
- Iterate through the binary string:↵
- If `1` is encountered:↵
- Assign it to a subsequence from `zero` (if available).↵
- Otherwise, create a new subsequence.↵
- If `0` is encountered:↵
- Assign it to a subsequence from `one` (if available).↵
- Otherwise, create a new subsequence.↵
- The maximum number used in our subsequences is the answer.↵
↵
### Complexity:↵
- Each character is processed once and assigned in **O(n)** time.↵
- Given the constraints, this approach is efficient.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
```python3↵
import sys ↵
↵
def solve():↵
↵
# Read input: length of binary string↵
n = int(sys.stdin.readline().strip())↵
↵
# Convert input string into a list of integers (0s and 1s)↵
nums = [int(i) for i in sys.stdin.readline().strip()]↵
↵
zero = [] # Tracks subsequences ending in 0↵
one = [] # Tracks subsequences ending in 1↵
ans = [] # Stores the assigned subsequence number for each character↵
maxi = 0 # Keeps track of the total number of subsequences used↵
↵
# Process each character in the binary string↵
for val in nums:↵
if val == 1: # If the current character is '1'↵
if zero:↵
# If there exists a subsequence ending in '0', use it↵
temp = zero.pop()↵
else:↵
# Otherwise, create a new subsequence↵
maxi += 1↵
temp = maxi ↵
↵
# Mark that this subsequence now ends in '1'↵
one.append(temp)↵
ans.append(temp)↵
↵
else: # If the current character is '0'↵
if one:↵
# If there exists a subsequence ending in '1', use it↵
temp = one.pop()↵
else:↵
# Otherwise, create a new subsequence↵
maxi += 1↵
temp = maxi ↵
↵
# Mark that this subsequence now ends in '0'↵
zero.append(temp)↵
ans.append(temp)↵
↵
# Print the total number of subsequences used↵
print(max(ans))↵
↵
# Print the assigned subsequence number for each character↵
print(*ans)↵
↵
q = int(sys.stdin.readline().strip())↵
↵
for _ in range(q):↵
solve()↵
``` ↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
#### [F. Nahom's Array Dilemma](https://codeforces.me/gym/594077/problem/F)↵
↵
↵
<spoiler summary = "Hint1">↵
If we have a list of subarrays where the element at index $i$ is the max, which subarrays should we check to be sufficient?↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
Checking subarrays which end or start at index $i$ is sufficient, so we can optimize our solution with this observation as the basis.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
Let's look at the problem from the perspective of each $a_i$. We want to check whether the sum of the subarrays, where $a_i$ is the maximum element, exceeds $a_i$ or not.↵
↵
Firstly, we must find out in which subarrays is $a_i$ the maximum. This involves finding the previous greater element index and the next greater element index of $i$, which can be done for all indices in $O(n)$ using monotonic stack. Take these indices as $x_i$, $y_i$.↵
↵
Take $(j,k)$, which represents the sum of a subarray which starts at index $j$ and ends at index $k$, where $j∈[x_i +1, i]$, $k∈[i,y_i−1]$. If $(j,k)>a_i$, then $(j,i−1)+(i,i)+(i+1,k)>a_i$, giving us $(j,i−1)+(i+1,k)>0$. Hence, at least one of the subarrays, $(j,i−1)$ or $(i+1,k)$ has a sum greater than $0$, which implies that one of subarrays $(j,i)$, $(i,k)$ has sum greater than $a_i$, so only checking subarrays which start or end at index $i$ suffices.↵
↵
To determine whether there exists a subarray where the sum exceeds its maximum value, we utilize a Monotonic Stack to efficiently find the previous greater element indices and Prefix Sums to enable quick subarray sum queries.↵
↵
For any index $i$, the monotonic stack ensures that:↵
↵
While processing $a_i$ , we pop all elements from the stack that are less than or equal to $a_i$.↵
This guarantees that for all popped indices, $a_i$ is the first greater element to their right.↵
For the last popped index $v$, we check the sum from $v$ to $(i-1)$ > $0$ If true, it implies that some subarray sum exceeds its maximum, violating the required condition. In this case, we immediately return $NO$ since at least one problematic subarray exists.↵
↵
$Why$ $This$ $is$ $Sufficient?$↵
↵
↵
The monotonic stack guarantees that we only check valid subarrays where the current element is the maximum, ensuring:↵
↵
No problematic subarray is missed.↵
↵
Minimal subarray checks, avoiding an exhaustive search.↵
↵
Since we apply the same check on both the original and reversed array, we ensure correctness across all possible subarrays.↵
↵
$Final$ $Steps$↵
↵
Process the array from left to right:↵
Use a monotonic stack to track the next greater elements.↵
As elements are popped, check if the suffix sum (from the popped index up to $i−1$) is greater than 0.↵
If true, print $NO$ and terminate early.↵
Reverse the array and repeat the process to handle Next greater elements efficiently.↵
↵
Time Complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
↵
def prevGreater(nums):↵
stack = []↵
pref = [0]↵
↵
for num in nums:↵
pref.append(pref[-1] + num)↵
↵
for i in range(n):↵
↵
while stack and nums[stack[-1]] <= nums[i]:↵
v = stack.pop()↵
↵
if pref[i] - pref[v]> 0:↵
return False↵
↵
stack.append(i)↵
↵
return True↵
↵
if prevGreater(nums) and prevGreater(nums[::-1]):↵
return "YES"↵
↵
return "NO"↵
↵
t = int(sys.stdin.readline().strip())↵
for _ in range(t):↵
print(solve())↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [A. The Ticket Booth](https://codeforces.me/gym/594077/problem/A)↵
↵
<spoiler summary = "Solution">↵
Simply put, the problem is asking us to represent $S$, as a summation of numbers from the set ${1, 2, 3, … ,n }$.↵
↵
Obviously there are many ways to do that, for example one might use $1$ $S$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.↵
↵
Since we have all the numbers from $1$ to $n$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $S$, until we get the sum of the selected elements equal to $S$. This ensures that we use the fewest possible numbers.↵
↵
This process can easily be represented by a ceil division of $S$ by $n$.↵
↵
because $⌈S/n⌉$ tells us how many times we would need to add the largest possible number (which is $n$) to reach or exceed $S$.↵
↵
Time complexity: $O(1)$.↵
Space complexity: $O(1)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n,S = map(int, input().split())↵
↵
print((S + n - 1) // n) ↵
```↵
</spoiler>↵
↵
↵
#### [B. Nafargi's Binary Reduction Game](https://codeforces.me/gym/594077/problem/B)↵
↵
<spoiler summary = "Solution">↵
The problem involves removing adjacent `01` or `10` pairs from a binary string until no more moves are possible. The goal is to find the minimum possible remaining length of the string.↵
↵
Stack-Based Solution:↵
Traverse the binary string while maintaining a stack.↵
If the stack is non-empty and the current character forms a removable pair (01 or 10) with the top of the stack, pop the stack.↵
Otherwise, push the current character onto the stack.↵
The size of the stack at the end represents the minimum remaining length.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input().strip())↵
s = input().strip()↵
stack = []↵
for char in s:↵
if stack and stack[-1] != char:↵
stack.pop() # Remove 01 or 10 pair↵
else:↵
stack.append(char) # Push character if no pair found↵
print(len(stack))↵
```↵
</spoiler>↵
↵
↵
#### [C. Permutation Minimization](https://codeforces.me/gym/594077/problem/C)↵
↵
<spoiler summary = "Solution">↵
<p>↵
We need the <b>deque</b> data structure to solve this problem. We iterate the given permutation starting from the first element and we append to the left of our <b>deque</b> either if it is empty or the element at the <b>0-th</b> index of our <b>deque</b> is larger than the current element we are about to add to our <b>deque</b>. Otherwise we append to the end of our <b>deque</b> because appending a larger number than what we currently have at the <b>0-th</b> index of our <b>deque</b> will definitly make our final answer <b>lexicographically larger</b>.↵
</p>↵
↵
<spoiler summary = "Time and space complexities">↵
<ul>↵
<li> <b> Time Complexity: O(n) </b> </li>↵
<li> <b> Space Complexity: O(n) </b> </li>↵
</ul>↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```↵
from collections import deque↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
ans = deque()↵
for num in arr:↵
if ans and num < ans[0]:↵
ans.appendleft(num)↵
else:↵
ans.append(num)↵
↵
print(*ans)↵
```↵
</spoiler>↵
↵
↵
#### [D. Meklit's Chat Screen](https://codeforces.me/gym/594077/problem/D)↵
↵
<spoiler summary="Hint 1">↵
- Think of a **queue** (FIFO structure) to store the most recent `k` unique chats.↵
- Use a **set** to quickly check if a friend's chat is already on the screen.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When a new chat arrives and the screen is full, **remove the oldest chat** before adding the new one.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The problem requires maintaining the most recent `k` unique chat messages in order. ↵
Key observations: ↵
1. If a friend sends multiple messages, only the first occurrence matters. ↵
2. If the chat screen is full (`k` elements), the oldest message is removed when a new unique message arrives. ↵
↵
### Approach:↵
- Use a **deque** (`chat_screen`) to store recent unique chats while maintaining order. ↵
- Use a **set** (`seen`) to track which friends are currently displayed. ↵
- Process each message: ↵
- If it's already in `seen`, ignore it.↵
- Otherwise: ↵
- If `chat_screen` is full, remove the **oldest** chat (last element). ↵
- Add the new chat to the **front** of `chat_screen` and update `seen`. ↵
- Print the final chat list. ↵
↵
This method ensures an **O(n) time complexity**, which is efficient for large inputs. ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
from collections import deque↵
↵
def chat_screen(n, k, messages):↵
chat_screen = deque()↵
seen = set()↵
↵
for id_i in messages:↵
if id_i not in seen:↵
if len(chat_screen) == k:↵
removed = chat_screen.pop()↵
seen.remove(removed)↵
↵
chat_screen.appendleft(id_i)↵
seen.add(id_i)↵
↵
print(len(chat_screen))↵
print(*chat_screen)↵
↵
n, k = map(int, input().split())↵
messages = list(map(int, input().split()))↵
chat_screen(n, k, messages)↵
↵
``` ↵
</spoiler>↵
↵
↵
#### [E. Minimum Subsequence](https://codeforces.me/gym/594077/problem/E)↵
↵
<spoiler summary="Hint 1">↵
- Think of maintaining **two lists** to track subsequences ending in `0` and `1`.↵
- A **greedy approach** helps in assigning characters to subsequences optimally.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
- If a `1` appears, assign it to a subsequence that previously ended in `0`.↵
- If a `0` appears, assign it to a subsequence that previously ended in `1`.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The problem requires dividing the binary string into the **minimum number** of subsequences ↵
such that each follows an alternating `0-1` or `1-0` pattern.↵
↵
1. Each character belongs to exactly **one** subsequence.↵
2. If a `1` appears, it should ideally continue a subsequence ending in `0`, and vice versa.↵
3. We can efficiently track and assign subsequences using two lists:↵
- `zero` → Stores subsequences ending in `0`.↵
- `one` → Stores subsequences ending in `1`.↵
↵
- Iterate through the binary string:↵
- If `1` is encountered:↵
- Assign it to a subsequence from `zero` (if available).↵
- Otherwise, create a new subsequence.↵
- If `0` is encountered:↵
- Assign it to a subsequence from `one` (if available).↵
- Otherwise, create a new subsequence.↵
- The maximum number used in our subsequences is the answer.↵
↵
### Complexity:↵
- Each character is processed once and assigned in **O(n)** time.↵
- Given the constraints, this approach is efficient.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
```python3↵
import sys ↵
↵
def solve():↵
↵
# Read input: length of binary string↵
n = int(sys.stdin.readline().strip())↵
↵
# Convert input string into a list of integers (0s and 1s)↵
nums = [int(i) for i in sys.stdin.readline().strip()]↵
↵
zero = [] # Tracks subsequences ending in 0↵
one = [] # Tracks subsequences ending in 1↵
ans = [] # Stores the assigned subsequence number for each character↵
maxi = 0 # Keeps track of the total number of subsequences used↵
↵
# Process each character in the binary string↵
for val in nums:↵
if val == 1: # If the current character is '1'↵
if zero:↵
# If there exists a subsequence ending in '0', use it↵
temp = zero.pop()↵
else:↵
# Otherwise, create a new subsequence↵
maxi += 1↵
temp = maxi ↵
↵
# Mark that this subsequence now ends in '1'↵
one.append(temp)↵
ans.append(temp)↵
↵
else: # If the current character is '0'↵
if one:↵
# If there exists a subsequence ending in '1', use it↵
temp = one.pop()↵
else:↵
# Otherwise, create a new subsequence↵
maxi += 1↵
temp = maxi ↵
↵
# Mark that this subsequence now ends in '0'↵
zero.append(temp)↵
ans.append(temp)↵
↵
# Print the total number of subsequences used↵
print(max(ans))↵
↵
# Print the assigned subsequence number for each character↵
print(*ans)↵
↵
q = int(sys.stdin.readline().strip())↵
↵
for _ in range(q):↵
solve()↵
``` ↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
#### [F. Nahom's Array Dilemma](https://codeforces.me/gym/594077/problem/F)↵
↵
↵
<spoiler summary = "Hint1">↵
If we have a list of subarrays where the element at index $i$ is the max, which subarrays should we check to be sufficient?↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
Checking subarrays which end or start at index $i$ is sufficient, so we can optimize our solution with this observation as the basis.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
Let's look at the problem from the perspective of each $a_i$. We want to check whether the sum of the subarrays, where $a_i$ is the maximum element, exceeds $a_i$ or not.↵
↵
Firstly, we must find out in which subarrays is $a_i$ the maximum. This involves finding the previous greater element index and the next greater element index of $i$, which can be done for all indices in $O(n)$ using monotonic stack. Take these indices as $x_i$, $y_i$.↵
↵
Take $(j,k)$, which represents the sum of a subarray which starts at index $j$ and ends at index $k$, where $j∈[x_i +1, i]$, $k∈[i,y_i−1]$. If $(j,k)>a_i$, then $(j,i−1)+(i,i)+(i+1,k)>a_i$, giving us $(j,i−1)+(i+1,k)>0$. Hence, at least one of the subarrays, $(j,i−1)$ or $(i+1,k)$ has a sum greater than $0$, which implies that one of subarrays $(j,i)$, $(i,k)$ has sum greater than $a_i$, so only checking subarrays which start or end at index $i$ suffices.↵
↵
To determine whether there exists a subarray where the sum exceeds its maximum value, we utilize a Monotonic Stack to efficiently find the previous greater element indices and Prefix Sums to enable quick subarray sum queries.↵
↵
For any index $i$, the monotonic stack ensures that:↵
↵
While processing $a_i$ , we pop all elements from the stack that are less than or equal to $a_i$.↵
This guarantees that for all popped indices, $a_i$ is the first greater element to their right.↵
For the last popped index $v$, we check the sum from $v$ to $(i-1)$ > $0$ If true, it implies that some subarray sum exceeds its maximum, violating the required condition. In this case, we immediately return $NO$ since at least one problematic subarray exists.↵
↵
$Why$ $This$ $is$ $Sufficient?$↵
↵
↵
The monotonic stack guarantees that we only check valid subarrays where the current element is the maximum, ensuring:↵
↵
No problematic subarray is missed.↵
↵
Minimal subarray checks, avoiding an exhaustive search.↵
↵
Since we apply the same check on both the original and reversed array, we ensure correctness across all possible subarrays.↵
↵
$Final$ $Steps$↵
↵
Process the array from left to right:↵
Use a monotonic stack to track the next greater elements.↵
As elements are popped, check if the suffix sum (from the popped index up to $i−1$) is greater than 0.↵
If true, print $NO$ and terminate early.↵
Reverse the array and repeat the process to handle Next greater elements efficiently.↵
↵
Time Complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
↵
def prevGreater(nums):↵
stack = []↵
pref = [0]↵
↵
for num in nums:↵
pref.append(pref[-1] + num)↵
↵
for i in range(n):↵
↵
while stack and nums[stack[-1]] <= nums[i]:↵
v = stack.pop()↵
↵
if pref[i] - pref[v]> 0:↵
return False↵
↵
stack.append(i)↵
↵
return True↵
↵
if prevGreater(nums) and prevGreater(nums[::-1]):↵
return "YES"↵
↵
return "NO"↵
↵
t = int(sys.stdin.readline().strip())↵
for _ in range(t):↵
print(solve())↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
