Priority Queue

In priority queue, each element in the queue has its own priority. When we insert item into queue, we have to assign priority value with it.

• Declaration

  priority_queue<int> pq; (creates a priority_queue, default it is equivalent to max heap)  
  // To create min Heap  
  priority_queue<int, vector<int>, greater<int> > pq;

• Size:

  int size = pq.size();

• Pushing an integer into a Priority queue:

  pq.push(x); (where x is an integer.The size increases by 1 after this.)

• Getting the maximum/minimum element from max/min priority queue

  pq.top()

• Popping the maximum/minimum element from max/min priority queue

  pq.pop(); (After this the size decreases by 1)

Try the following example in the editor below.

Given an array of integers A representing the length of ropes.

You need to connect these ropes into one rope. The cost of connecting two ropes is equal to the sum of their lengths.

Find and return the minimum cost to connect these ropes into one rope.

Constraints

1 <= length of the array <= 100000
1 <= A[i] <= 1000

Input Format

The only argument given is the integer array A.

Output Format

Return an integer denoting the minimum cost to connect these ropes into one rope.

Sample Input

A = [1, 2, 3, 4, 5]

Sample Output

33