Initailly I thought of to implement memoization solution for this problem, but constraints are big. So, What could be the possible solution for this? Any greedy approach ? Here is the Question.
You are given an array A of N integers that are not necessarily distinct. Additionally you have a pointer p that initially points to the first element of A.
You are allowed to perform following types of operations:
Increment p to point to next element
Decrement p to point to previous element
Erase the current element p is pointing to. Additionally after the erase operation you must choose whether p will point to the previous or next element.
Find the minimum number of operations required to erase all the elements in non-decrrasing order
Input format:
The first line contains an integer N denoting the number of elements in A
Each line i of the N Subsequent lines contain an integer describing A[i]
1<=N<=10^5
1<=N<=10^9
Sample Input ;
1
1
Sample Output:
1
Here since only 1 element is there we erase it in 1 operation
Sample Input
4
1
2
3
4
Sample Output
4
The 4 operations are
-> erase and move right
-> erase and move right
-> erase and move right
-> erase finish
Sample Input
5
2
1
3
3
2
Sample Output
8
Here initially array A= [2,1,3,3,2]
Pointer is at first position
-> Incremenr pointer
-> Erase the current element and set the pointer to previous element
->Erae the current element and set the pointer to next element
-> Increment pointer
-> Increment pointer
-> Erase the current element and set the pointer to previous element
-> Erase the current element and set the pointer to the previous element
-> Erase the current element and end afterward. The array is empty now
The elements were erased in non decreasing order [1,2,2,3,3]