class MyStack {

private int[] arr;

private int top;

public MyStack() {
arr = new int[1000];
top = -1;
}

public void push(int x) {

if(top < [Link]-1){
//stack is not full
arr[++top] = x;
}
}

public int pop() {

if(top == -1){
//stack is empty
return -1;
}
else{
return arr[top--];
}
}
}
class MyQueue {

int front, rear;

int arr[] = new int[100005];

MyQueue() {
front = 0;
rear = 0;
}

// Function to push an element x in a queue.

void push(int x) {
if(rear < [Link]){
arr[rear++] = x;
}
else{
//queue is full
}
}

// Function to pop an element from queue and return that element.

int pop() {
if (front == rear) {
// Queue is empty
return -1;
}
return arr[front++];
}
}
class MyQueue {

int front, rear;

int arr[] = new int[100005];

MyQueue() {
front = 0;
rear = 0;
}

// Function to push an element x in a queue.

void push(int x) {
int nextRear = (rear + 1) % [Link];

if (nextRear != front) {
arr[rear] = x;
rear = nextRear;
}
// else: Queue is full, do nothing
}

// Function to pop an element from queue and return that element.

int pop() {
if (front == rear) {
// Queue is empty
return -1;
}
int val = arr[front];
front = (front + 1) % [Link];
return val;
}
}
class MyQueue {

int front, rear;

int arr[] = new int[100005];

MyQueue() {
front = 0;
rear = 0;
}

// Function to push an element x in a queue.

void push(int x) {
int nextRear = (rear + 1) % [Link];

if (nextRear != front) {
arr[rear] = x;
rear = nextRear;
}
// else: Queue is full, do nothing
}

// Function to pop an element from queue and return that element.

int pop() {
if (front == rear) {
// Queue is empty
return -1;
}
int val = arr[front];
front = (front + 1) % [Link];
return val;
}
}
class MyStack {
Queue<Integer> q;

public MyStack() {
this.q = new LinkedList<>();
}

public void push(int x) {

int n = [Link]();

[Link](x);

for(int i=0;i<n;i++){
[Link]([Link]());
}
}

public int pop() {

if([Link]()){
return -1;
}

return [Link]();
}

public int top() {

if([Link]()){
return -1;
}

return [Link](); //just seeing the top element

}

public boolean empty() {

return [Link]();
}
}
class MyQueue {
Stack<Integer> inStack; // for push operations
Stack<Integer> outStack; // for pop/peek operations

public MyQueue() {
[Link] = new Stack<>();
[Link] = new Stack<>();
}

public void push(int x) {

// Simply push to inStack - O(1)
[Link](x);
}

public int pop() {

// Ensure outStack has elements for popping
if ([Link]()) {
// Transfer all elements from inStack to outStack
while (![Link]()) {
[Link]([Link]());
}
}

if ([Link]()) {
return -1; // Queue is empty
}

return [Link]();
}

public int peek() {

// Ensure outStack has elements for peeking
if ([Link]()) {
// Transfer all elements from inStack to outStack
while (![Link]()) {
[Link]([Link]());
}
}

if ([Link]()) {
return -1; // Queue is empty
}

return [Link]();
}

public boolean empty() {

return [Link]() && [Link]();
}
}
class MyStack {
// class StackNode {
// int data;
// StackNode next;
// StackNode(int a) {
// data = a;
// next = null;
// }
// }
StackNode top;

// Function to push an integer into the stack.

void push(int a) {
//make a new node
StackNode node = new StackNode(a);
[Link] = top;

top = node;
}

// Function to remove an item from top of the stack.

int pop() {
if(top == null){
return -1; //stack is empty
}

int topValue = [Link];

top = [Link]; //remove the node

return topValue;
}
}
class MyQueue
{
QueueNode front, rear;

//Function to push an element into the queue.

void push(int a)
{
QueueNode node = new QueueNode(a);

if(rear == null){
//queue is empty
front = node;
rear = node;
}
else{
[Link] = node;
rear = node;
}

//Function to pop front element from the queue.

int pop()
{
if(front == null){
//queue is empty
return -1;
}

int frontVal = [Link]; //take the value

front = [Link]; //move the front

if(front == null){
//it means that was the only element in queue
rear = null;
}

return frontVal;
}
}
class Solution {
public boolean isValid(String s) {
int n = [Link]();
if(n%2 == 1){
//n is odd, that means parantheses is not balanced
return false;
}

Stack<Character> st = new Stack<>();

for(int i=0;i<n;i++){
char c = [Link](i);

if(c=='(' || c=='{' || c=='['){

//any type of open, the push
[Link](c);
}
else{
if([Link]()){
//no opening bracket but still, we encountered a closing bracket
return false;
}

char popped=[Link]();
if((c==')'&&popped=='(')||(c=='}'&&popped=='{')||(c==']'&&popped=='['))
{
//ok, fine we got a valid bracket pair
continue;
}
else{
//bracket pair is not valid
return false;
}
}
}

//after all if any bracket is left, then parentheses is invalid

return [Link]();
}
}
class MinStack {

// Custom Node class to store:

// - val: the actual value
// - min: the minimum value in the stack till this node
// - next: pointer to the next node in the stack
private class Node {
int val;
int min;
Node next;

public Node(int val, int min) {

[Link] = val;
[Link] = min;
[Link] = null;
}
}

Node top;

// Constructor
public MinStack() {
[Link] = null;
}

// Push a new value onto the stack

public void push(int val) {
if (top == null) {
// Stack is empty, so this value is the min as well
top = new Node(val, val);
}
else {
// Compare new value with current min and create a new node
// This way, each node "remembers" the min up to that point
Node newTop = new Node(val, [Link](val, [Link]));
[Link] = top; // Link new node to the previous top
top = newTop; // Update top to the new node
}
}

// Pop the top element from the stack

public void pop() {
if (top != null) {
top = [Link]; // Move top to the next node
}
// If top is already null, stack is empty; do nothing
}

// Return the value at the top of the stack

public int top() {
if (top != null) {
return [Link];
}
return -1; // Stack is empty
}

// Return the current minimum element in the stack

public int getMin() {
if (top != null) {
return [Link];
}
return -1; // Stack is empty
}
}
class Solution {
public static String infixToPostfix(String s) {
int n = [Link]();
StringBuilder sb = new StringBuilder(); // For building the postfix expression
Stack<Character> st = new Stack<>(); // Stack to store operators and parentheses

for (int i = 0; i < n; i++) {

char c = [Link](i);

if (c == '(') {
[Link]('('); // Push opening bracket
}
else if (c == ')') {
// Pop until matching '(' is found
while ([Link]() != '(') {
[Link]([Link]());
}
[Link](); // Remove the '(' from the stack
}
else if (isOperator(c)) {
// Pop higher or equal priority operators before pushing current
while (![Link]() && [Link]() != '(' && priority(c) <= priority([Link]())) {
[Link]([Link]());
}
[Link](c); // Push current operator
}
else {
[Link](c); // Append operand (variable/constant) directly to output
}
}

// Pop any remaining operators from the stack

while (![Link]()) {
[Link]([Link]());
}

return [Link](); // Final postfix expression

}

// Checks if a character is a valid operator

private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

// Returns precedence of operators (higher value = higher priority)

private static int priority(char op) {
if (op == '^') return 3;
else if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 1;
return -1;
}
}
class Solution {
public static String infixToPrefix(String s) {
int n = [Link]();
s = reverseAndSwapBrackets(s);

StringBuilder sb = new StringBuilder();

Stack<Character> st = new Stack<>();

for(int i = 0; i < n; i++){

char c = [Link](i);

if(c == '('){
[Link]('(');
}
else if(c == ')'){
while(![Link]() && [Link]() != '('){
[Link]([Link]());
}

if(![Link]()) {
[Link](); // pop out the open bracket
}
}
else if(isOperator(c)){
// For prefix: use strict less than (<) instead of less than or equal (<=)
// This ensures right associativity for operators like ^ in prefix notation
while(![Link]() && [Link]() != '(' && priority(c) < priority([Link]())){
[Link]([Link]());
}
[Link](c);
}
else{
// character (operand)
[Link](c);
}
}

// Pop remaining operators from stack

while(![Link]()){
[Link]([Link]());
}

return [Link]().toString();
}

public static String reverseAndSwapBrackets(String s) {

StringBuilder sb = new StringBuilder();

for (int i = [Link]() - 1; i >= 0; i--) {

char c = [Link](i);

if (c == '(') {
[Link](')');
}
else if (c == ')') {
[Link]('(');
} else {
[Link](c);
}
}

return [Link]();
}

private static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

private static int priority(char op) {

if(op == '^'){
return 3;
}
else if(op == '/' || op == '*'){
return 2;
}
else if(op == '+' || op == '-'){
return 1;
}

return -1;
}
}
class Solution {
static String postToInfix(String exp) {
int n = [Link]();

Stack<String> st = new Stack<>();

for(int i=0;i<n;i++){
char c = [Link](i);

if(isOperator(c)){
String b = [Link]();
String a = [Link]();
[Link]("("+a+c+b+")");
}
else{
[Link]([Link](c));
}
}

// Final expression is on top of the stack

return [Link]();
}

private static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
}
class Solution {
static String preToInfix(String pre_exp) {
int n = pre_exp.length();

Stack<String> st = new Stack<>();

for(int i=n-1;i>=0;i--){
char c = pre_exp.charAt(i);

if(isOperator(c)){
String b = [Link]();
String a = [Link]();
[Link]("("+b+c+a+")");
}
else{
[Link]([Link](c));
}
}

// Final expression is on top of the stack

return [Link]();
}

private static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
}
class Solution {
static String postToPre(String post_exp) {
int n = post_exp.length();

Stack<String> st = new Stack<>();

for(int i=0;i<n;i++){
char c = post_exp.charAt(i);

if(isOperator(c)){
String b = [Link]();
String a = [Link]();
[Link](c+a+b);
}
else{
[Link]([Link](c));
}
}

// Final expression is on top of the stack

return [Link]();
}

private static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
}
class Solution {
static String preToPost(String pre_exp) {
int n = pre_exp.length();

Stack<String> st = new Stack<>();

for(int i=n-1; i>=0; i--){

char c = pre_exp.charAt(i);

if(isOperator(c)){
String b = [Link]();
String a = [Link]();
[Link](b+a+c);
}
else{
[Link]([Link](c));
}
}

// Final expression is on top of the stack

return [Link]();
}

private static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
}
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] ans = new int[[Link]];
int[] nge = new int[10001]; // Index = value in nums2, value = its NGE

Stack<Integer> st = new Stack<>();

// Process nums2 to find NGE for each element

for (int i = [Link] - 1; i >= 0; i--) {
int curr = nums2[i];

// Remove all smaller or equal elements from the stack

while (![Link]() && [Link]() <= curr) {
[Link]();
}

// Stack top is the next greater element, if stack not empty

nge[curr] = [Link]() ? -1 : [Link]();

// Push current element onto the stack

[Link](curr);
}

// Construct result for nums1 using the precomputed NGE array

for (int i = 0; i < [Link]; i++) {
ans[i] = nge[nums1[i]];
}

return ans;
}
}
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = [Link];
int[] ans = new int[n];

Stack<Integer> st = new Stack<>();

//currently in the repeated array

for(int i=n-1; i>=0; i--){

// Remove all smaller or equal elements from the stack

while (![Link]() && [Link]() <= nums[i]) {
[Link]();
}

// Push current element onto the stack

[Link](nums[i]);
}

//now in the actual array

for(int i=n-1; i>=0; i--){

// Remove all smaller or equal elements from the stack

while (![Link]() && [Link]() <= nums[i]) {
[Link]();
}

ans[i] = ([Link]() ? -1 : [Link]());

// Push current element onto the stack

[Link](nums[i]);
}

return ans;
}
}
class Solution {
public void nextSmaller(int arr[]) {
Stack<Integer> st = new Stack<>();

// Process arr to find NSE for each element

for (int i = [Link] - 1; i >= 0; i--) {
int cur = arr[i];

// Remove all greater or equal elements from the stack

while (![Link]() && [Link]() >= arr[i]) {
[Link]();
}

// Stack top is the next smaller element, if stack not empty

arr[i] = [Link]() ? -1 : [Link]();

// Push current element onto the stack

[Link](cur);
}
}
}
class Solution {
public static int[] count_NGEs(int N, int arr[], int queries, int indices[]) {
// Output array to store result for each query
int[] ans = new int[queries];

// Process each query one by one

for (int i = 0; i < queries; i++) {
int count = 0;

// For the current index, count elements to its right that are greater
for (int j = indices[i] + 1; j < N; j++) {
if (arr[j] > arr[indices[i]]) {
count++;
}
}

// Store the count in the answer array

ans[i] = count;
}

return ans;
}
}
class Solution {
public int trap(int[] height) {
int n = [Link];

int[] prefixMaximum = new int[n];

int[] suffixMaximum = new int[n];

prefixMaximum[0] = height[0];
for(int i=1; i<n; i++){
prefixMaximum[i] = [Link](height[i], prefixMaximum[i-1]);
}

suffixMaximum[n-1] = height[n-1];
for(int i=n-2; i>=0; i--){
suffixMaximum[i] = [Link](height[i], suffixMaximum[i+1]);
}

int waterUnits = 0;
for(int i=0; i<n; i++){
int leftMax = prefixMaximum[i];
int rightMax = suffixMaximum[i];

if(leftMax>height[i] && rightMax>height[i]){

//if the condition inside if is true othen only that index can hold water

waterUnits += [Link](leftMax, rightMax) - height[i];

}
}

return waterUnits;
}
}

class Solution {
public int trap(int[] height) {
int n = [Link];

int left = 0; // Pointer starting from the left

int right = n - 1; // Pointer starting from the right

int leftMax = 0; // Highest bar seen so far from the left

int rightMax = 0; // Highest bar seen so far from the right

int waterUnits = 0; // Accumulator for total trapped water

while (left < right) {

// Update the max height from left and right
leftMax = [Link](leftMax, height[left]);
rightMax = [Link](rightMax, height[right]);

// The amount of water trapped at any index is determined by

// the minimum of leftMax and rightMax minus the current height

if (leftMax <= rightMax) {

waterUnits += leftMax - height[left];
left++;
}
else {
waterUnits += rightMax - height[right];
right--; // Move right pointer inward
}
}

return waterUnits;
}
}
class Solution {
public int sumSubarrayMins(int[] arr) {
int mod = (int)1e9 + 7;
int n = [Link];

int ans = 0;

for(int i=0;i<n;i++){
int minInSubarr = Integer.MAX_VALUE;
for(int j=i;j<n;j++){
minInSubarr = [Link](minInSubarr, arr[j]);
ans = (ans + minInSubarr) % mod;
}
}

return ans;
}
}
class Solution {
public int sumSubarrayMins(int[] arr) {
int mod = (int)1e9 + 7;
int n = [Link];

int[] nextSmallerElementIndex = generateNSEI(arr);

int[] prevSmallerOrEqualElementIndex = generatePSOEEI(arr);

long ans = 0;

for(int i=0; i<n; i++){

long leftCount = i - prevSmallerOrEqualElementIndex[i];
long rightCount = nextSmallerElementIndex[i] - i;
long contribution = (arr[i] * leftCount * rightCount) % mod;
ans = (ans + contribution) % mod;
}

return (int)ans;
}

private int[] generateNSEI(int[] arr){

int n = [Link];

int[] nextSmallerElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=n-1; i>=0; i--){

while(![Link]() && arr[i] <= arr[[Link]()]){
[Link]();
}

nextSmallerElementIndex[i] = [Link]() ? n : [Link]();

[Link](i);
}

return nextSmallerElementIndex;
}

private int[] generatePSOEEI(int[] arr){

int n = [Link];

int[] prevSmallerOrEqualElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=0; i<n; i++){

while(![Link]() && arr[i] < arr[[Link]()]){
[Link]();
}

prevSmallerOrEqualElementIndex[i] = [Link]() ? -1 : [Link]();

[Link](i);
}

return prevSmallerOrEqualElementIndex;
}
}
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int n = [Link];
Stack<Integer> st = new Stack<>();

for(int i=0; i<n; i++){

if(asteroids[i] > 0){
[Link](asteroids[i]);
}
else{
while(![Link]() && [Link]()>0 && ([Link]() < -asteroids[i])){
[Link]();
}
//now either the stack is empty (or) the element in the stack is a
negative element (or) the element in the stack is more powerful

if(![Link]() && [Link]() == -asteroids[i]){

//if the asteroid is of same size
[Link]();

//destroy both
}
else if([Link]() || [Link]()<0){
//if the stack is empty (or) the asteroid is a negative element
[Link](asteroids[i]);
}
//if the stack asteroid is positive do nothing, it means the
current asteroid will be destroyed
}
}

// Convert stack to array

int[] ans = new int[[Link]()];
for (int i = [Link]() - 1; i >= 0; i--) {
ans[i] = [Link]();
}

return ans;
}
}
public long subArrayRanges(int[] nums) {
return sumSubarrayMax(nums) - sumSubarrayMin(nums);
}
// codes for Sum of Subarray Minimums
private long sumSubarrayMin(int[] arr){
int n = [Link];

int[] nextSmallerElementIndex = generateNSEI(arr);

int[] prevSmallerOrEqualElementIndex = generatePSOEEI(arr);

long ans = 0;

for(int i=0; i<n; i++){

long leftCount = i - prevSmallerOrEqualElementIndex[i];
long rightCount = nextSmallerElementIndex[i] - i;
ans = ans + arr[i]*leftCount*rightCount;
}

return ans;
}

private int[] generateNSEI(int[] arr){

int n = [Link];

int[] nextSmallerElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=n-1; i>=0; i--){

while(![Link]() && arr[i] <= arr[[Link]()]){
[Link]();
}

nextSmallerElementIndex[i] = [Link]() ? n : [Link]();

[Link](i);
}

return nextSmallerElementIndex;
}

private int[] generatePSOEEI(int[] arr){

int n = [Link];

int[] prevSmallerOrEqualElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=0; i<n; i++){

while(![Link]() && arr[i] < arr[[Link]()]){
[Link]();
}

prevSmallerOrEqualElementIndex[i] = [Link]() ? -1 : [Link]();

[Link](i);
}

return prevSmallerOrEqualElementIndex;
}

// codes for Sum of Subarray Maximums

private long sumSubarrayMax(int[] arr){
int n = [Link];

int[] nextGreaterElementIndex = generateNGEI(arr);

int[] prevGreaterOrEqualElementIndex = generatePGOEEI(arr);

long ans = 0;

for(int i=0; i<n; i++){

long leftCount = i - prevGreaterOrEqualElementIndex[i];
long rightCount = nextGreaterElementIndex[i] - i;
ans = ans + arr[i]*leftCount*rightCount;
}

return ans;
}

private int[] generateNGEI(int[] arr){

int n = [Link];

int[] nextGreaterElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=n-1; i>=0; i--){

while(![Link]() && arr[i] >= arr[[Link]()]){
[Link]();
}

nextGreaterElementIndex[i] = [Link]() ? n : [Link]();

[Link](i);
}

return nextGreaterElementIndex;
}

private int[] generatePGOEEI(int[] arr){

int n = [Link];

int[] prevGreaterOrEqualElementIndex = new int[n];

Stack<Integer> st = new Stack<>();

for(int i=0; i<n; i++){

while(![Link]() && arr[i] > arr[[Link]()]){
[Link]();
}

prevGreaterOrEqualElementIndex[i] = [Link]() ? -1 : [Link]();

[Link](i);
}

return prevGreaterOrEqualElementIndex;
}
class Solution {
public String removeKdigits(String num, int k) {
int n = [Link]();
if(k == n){
return "0"; //fast exit, we directly know 0 is the ans
}

Stack<Character> st = new Stack<>();

for (int i = 0; i < n; i++) {

char c = [Link](i);

// Pop digits while the current digit is smaller and we still have k to remove
while (k > 0 && ![Link]() && [Link]() > c) {
[Link]();
k--;
}

[Link](c);
}

// If still k digits to remove, remove from end (largest digits)

while (k > 0 && ![Link]()) {
[Link]();
k--;
}

// Build the result

StringBuilder sb = new StringBuilder();
while (![Link]()) {
[Link]([Link]());
}

[Link]();

// Remove leading zeros

while ([Link]() > 0 && [Link](0) == '0') {
[Link](0);
}

// If result is empty, return "0"

return [Link]() == 0 ? "0" : [Link]();
}
}
class Solution {
public int largestRectangleArea(int[] heights) {
int n = [Link];

int largestRectArea = 0;

for (int i = 0; i < n; i++) {

// Find the index of the previous smaller element (to the left)
int prevSmallerElementIndex = i;
while (prevSmallerElementIndex >= 0 && heights[i] <= heights[prevSmallerElementIndex]) {
prevSmallerElementIndex--;
}

// Find the index of the next smaller element (to the right)
int nextSmallerElementIndex = i;
while (nextSmallerElementIndex < n && heights[i] <= heights[nextSmallerElementIndex]) {
nextSmallerElementIndex++;
}

int width = nextSmallerElementIndex - prevSmallerElementIndex - 1;

int area = heights[i] * width;

largestRectArea = [Link](largestRectArea, area);

}

return largestRectArea;
}
}
class Solution {
public int largestRectangleArea(int[] heights) {
int n = [Link];

Stack<Integer> st = new Stack<>();

//pre-computing prevSmallerElementIndex
int[] prevSmallerElementIndex = new int[n];
for(int i=0; i<n; i++){
while(![Link]() && heights[[Link]()]>=heights[i]){
[Link]();
}

prevSmallerElementIndex[i] = [Link]() ? -1 : [Link]();

[Link](i); //push the index

}

[Link](); //clear the stack for next use

//pre-computing nextSmallerElementIndex
int[] nextSmallerElementIndex = new int[n];
for(int i=n-1; i>=0; i--){
while(![Link]() && heights[[Link]()]>=heights[i]){
[Link]();
}

nextSmallerElementIndex[i] = [Link]() ? n : [Link]();

[Link](i); //push the index

}

//now traverse and find the max area

int largestRectArea = 0;

for (int i = 0; i < n; i++) {

int width = nextSmallerElementIndex[i] - prevSmallerElementIndex[i] - 1;
int area = heights[i] * width;

largestRectArea = [Link](largestRectArea, area);

}

return largestRectArea;
}
}
class Solution {
public int largestRectangleArea(int[] heights) {
int n = [Link];
Stack<Integer> st = new Stack<>(); // stack to store indices
int maxArea = 0;

// We process all bars and one extra imaginary bar of height 0 at the
end
for (int i = 0; i <= n; i++) {
// Use 0 as the height for the imaginary bar beyond the end
int currHeight = (i == n) ? 0 : heights[i];

// If the current bar is smaller than the one on top of stack,

// we have found the 'next smaller' for the top of stack
while (![Link]() && currHeight < heights[[Link]()]) {
int height = heights[[Link]()]; // height of the rectangle
int nextSmallerElementIndex = i; // current index is
the next smaller
int prevSmallerElementIndex = [Link]() ? -1 : [Link](); //
previous smaller

int width = nextSmallerElementIndex - prevSmallerElementIndex -

1;
int area = height * width;

maxArea = [Link](maxArea, area);

}

[Link](i);
}

return maxArea;
}
}
class Solution {
public int maximalRectangle(char[][] matrix) {
int rows = [Link];
int cols = matrix[0].length;

int[][] twoDimPrefixSum = new int[rows][cols];

for(int j=0; j<cols; j++){

//for each column find a prefix sum downward
for(int i=0; i<rows; i++){
if(matrix[i][j]=='0'){
twoDimPrefixSum[i][j] = 0;
}
else{
if(i==0){
twoDimPrefixSum[i][j] = 1;
}
else{
twoDimPrefixSum[i][j] = 1 + twoDimPrefixSum[i-1][j];
}
}
}
}
//now the 2D-Prefix Sum is prepared

int ans = 0;
for(int i=0; i<rows; i++){
ans = [Link](ans, largestRectangleArea(twoDimPrefixSum[i]));
}

return ans;
}

private int largestRectangleArea(int[] heights){

int n = [Link];
Stack<Integer> st = new Stack<>(); // stack to store indices
int maxArea = 0;

// We process all bars and one extra imaginary bar of height 0, just to process those bars
// that did not have any nextSmallerElement

for(int i=0; i<=n; i++){

int curHeight = i==n ? 0 : heights[i];

while(![Link]() && heights[[Link]()]>curHeight){

int height = heights[[Link]()]; //height of the rect that is to be popped

int nextSmallerElementIndex = i;
int prevSmallerElementIndex = [Link]() ? -1 : [Link]();

int width = nextSmallerElementIndex - prevSmallerElementIndex - 1;

int area = width * height;

maxArea = [Link](maxArea, area);

}

[Link](i);
}

return maxArea;
}
}
class StockSpanner {

ArrayList<Integer> prices;

public StockSpanner() {
[Link] = new ArrayList<>();
}

public int next(int price) {

int count = 1;
int n = [Link]();

for(int i=n-1; i>=0; i--){

if([Link](i) <= price){
count++;
}
else{
break;
}
}

[Link](price);

return count;
}
}
class StockSpanner {

Stack<int[]> st; //{value,index}

int curIdx;

public StockSpanner() {
[Link] = new Stack<>();
curIdx = -1; //-1 denotes the stock market has just opened no days
//curIdx will be the index of the today
}

public int next(int price) {

[Link]++;

while(![Link]() && [Link]()[0] <= price){

[Link]();
}

int ans = curIdx - ([Link]() ? -1 : [Link]()[1]);

[Link](new int[]{price, curIdx});

return ans;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//total number of subarrays will be n - k + 1
int n = [Link];
int[] ans = new int[n-k+1];

for(int i=0; i<n-k+1; i++){

int max = Integer.MIN_VALUE;
for(int j=0; j<k; j++){
max = [Link](max, nums[i+j]);
}

ans[i] = max;
}

return ans;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = [Link];
int[] ans = new int[n-k+1];

Deque<Integer> dq = new ArrayDeque<>();

for(int i=0;i<n;i++){
//the elements before i-k (including) can't be the part of window
while(![Link]() && [Link]() <= i-k){
[Link]();
}

//Remove all indices from the back whose corresponding values are smaller than nums[i]
// Because they cannot be the max if nums[i] is greater

//but if the cur value is smaller than the deque last, then it may become the max
//(after the element which is now max, is moved out of window)
while(![Link]() && nums[[Link]()] <= nums[i]){
[Link]();
}

[Link](i); //add the current index to the back

if(i < k-1){

continue; //k elements have not yet completed
}

ans[i - k + 1] = nums[[Link]()]; //add the max elemnt to ans

}

return ans;
}
}
class Solution {
public int celebrity(int mat[][]) {
int n = [Link];

int[] numPplKnowsMe = new int[n];

int[] numPplIKnow = new int[n];

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mat[i][j] == 1){
numPplIKnow[i]++;
numPplKnowsMe[j]++;
}
}
}

//both arrays are now filled

//if numPplKnowsMe[i]=n and numPplIKnow[i]=1 (basically myself)
//then it means i is celebrity

for(int i=0; i<n; i++){

if(numPplKnowsMe[i]==n && numPplIKnow[i]==1){
return i;
}
}

return -1; //no celebrity

}
}
class Solution {
public int celebrity(int mat[][]) {
int n = [Link];
int top = 0;
int bottom = n-1;

while(top < bottom){

if(mat[top][bottom] == mat[bottom][top]){
//both either 1 or 0

//either both knows each other, then they both can't be celeb

//or if no one knows each other then also no one can be celeb,
// because there will be 1 person left that didn't know the other
top++;
bottom--;
}
else if(mat[top][bottom] == 1){
//does the top knows bottom
//if yes top can't be celebrity
top++;
}
else if(mat[bottom][top] == 1){
//does the bottom knows top
//if yes bottom can't be celebrity
bottom--;
}
}

//loop ended
if(top > bottom){
//we don't have any celebrity candidate
return -1;
}

//if that is not the case the top=bottom

for(int i=0; i<n; i++){
if(top!=i && (mat[top][i] != 0 || mat[i][top] != 1)){
return -1;
}
}

return top;
}
}
class LRUCache {
Map<Integer,Integer> cache;
int capacity;

public LRUCache(int capacity) {

[Link] = capacity;
[Link] = new LinkedHashMap<>();
}

public int get(int key) {

Integer value = [Link](key);
if (value != null) {
// Move to end (most recent) by removing and re-adding
[Link](key);
[Link](key, value);
return value;
}

return -1; //key was abset

}

public void put(int key, int value) {

if([Link](key) != null){
//over-writing
[Link](key); //remove the old one
[Link](key, value); //put the new one to the end
}
else if([Link](key) == null){
//the key is new

if([Link]() == capacity){
//we do not have space in cache

Integer firstKey = [Link]().iterator().next();

[Link](firstKey);

[Link](key, value); //put the new one to the end

}
else{
//we have space in cache
[Link](key, value); //put the new one to the end
}
}
}
}
//implementation of Node and DLL is given below
class LFUCache {
int capacity; //capacity of Cache memory
int minFreq; //keeping the track of least frequently used block
Map<Integer, DoublyLinkedList> freqMap; //for each frequency have a DLL
Map<Integer, Node> keyMap; //will map a key to its correcponding node

public LFUCache(int capacity) {

[Link] = capacity;
[Link] = 0;
[Link] = new HashMap<>();
[Link] = new HashMap<>();
}

public int get(int key) {

if([Link](key)){
Node block = [Link](key); //get the block

int oldFreq = [Link];

int newFreq = oldFreq+1;

// Remove from block from old frequency list

DoublyLinkedList oldList = [Link](oldFreq);
[Link](block);

// If this was the only node in oldList list, and that freq was the minimum
//update minFreq
if([Link] == 0 && oldFreq == minFreq) {
minFreq++;
}

[Link] = newFreq; //increase the frequency

//add this node to the newFreq DLL

DoublyLinkedList newList = [Link](newFreq);
if(newList == null){
//if that frequcny is never encountered, so list would not be present
[Link](newFreq, new DoublyLinkedList());
}

[Link](newFreq).addNode(block); //now safely add to the DLL of newFreq

return [Link];
}

return -1; //this key is not in cache

}

public void put(int key, int value) {

if([Link](key)){
// Key exists, update value and frequency

Node block = [Link](key); //get the block

int oldFreq = [Link];

int newFreq = oldFreq+1;

// Remove from block from old frequency list

DoublyLinkedList oldList = [Link](oldFreq);
[Link](block);

// If this was the only node in oldList list, and that freq was the minimum
//update minFreq
if([Link] == 0 && oldFreq == minFreq) {
minFreq++;
}

[Link] = newFreq; //increase the frequency

[Link] = value; //update the new value

//add this node to the newFreq DLL

DoublyLinkedList newList = [Link](newFreq);
if(newList == null){
//if that frequcny is never encountered, so list would not be present
[Link](newFreq, new DoublyLinkedList());
}

[Link](newFreq).addNode(block); //now safely add to the DLL of newFreq

}
else{
//New key
if([Link]() == capacity){
//we need to remove any block
DoublyLinkedList minFreqList = [Link](minFreq);

// Remove the least recently used node from LFU list (from tail)
Node nodeToRemove = [Link](); //

// Remove from keyMap

[Link]([Link]);
}

//add the new block

Node newNode = new Node(key, value);
[Link](key, newNode);

DoublyLinkedList dllForFreq1 = [Link](1);

if(dllForFreq1 == null){
[Link](1, new DoublyLinkedList());
}
[Link](1).addNode(newNode); //now safely add newNode to the DLL of 1

minFreq = 1; //obv if a new block is created it is accessed for the least time (i.e 1)
}
}
}
//Implementation for DLL
class Node {
int key;
int value;
int freq;

Node prev;
Node next;

public Node(int key, int value) {

[Link] = key;
[Link] = value;
[Link] = 1;

[Link] = null;
[Link] = null;
}
}

class DoublyLinkedList {
Node head;
Node tail;
int size;

public DoublyLinkedList() {
head = new Node(0, 0); // dummy head
tail = new Node(0, 0); // dummy tail
[Link] = tail;
[Link] = head;
size = 0;
}

//addition in O(1)
void addNode(Node node) {
[Link] = [Link];
[Link] = head;
[Link] = node;
[Link] = node;
size++;
}

//deletion in O(1)
void removeNode(Node node) {
[Link] = [Link];
[Link] = [Link];
//node doesn't havy anything pointing to it, so GC will trash it out
size--;
}

//O(1)
Node removeLast() {
if (size == 0){
return null;
}
Node last = [Link];
removeNode(last); //size will be decresed in the removeNode Call
return last;
}
}