# Largest Area Histogram 2

hard

1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the height of bars in a bar chart. 3. You are required to find and print the area of largest rectangle in the histogram. Challenge. Could u solve it in one iteration. Note. This question is same as Largest Area Histogram just the constrains are higher.

## Constraints

1. 1 <= heights.length <= 10^5 2. 0 <= heights[i] <= 10^4

## Format

### Input

Input is managed for you

### Output

Output is managed for you

## Example

Sample Input

6
2
1
5
6
2
3

### Sample Output

10