← 返回 microsoft 的题目列表Final Prices with Next Less-or-Equal Discount + Indices Sold at Full Price
类型：online_judge
Given an array prices of length n. For each item i, its final price is determined as follows:
Find the first index j > i such that prices[j] <= prices[i]. If it exists, final price is prices[i] - prices[j].
Otherwise, the item is sold at full price prices[i].
Output two lines:
The sum of all final prices.
The indices (0-based, increasing) of items sold at full price. Print an empty line if none.
Input format (suggested)
Line 1: integer n
Line 2: n integers prices[i]
Output format
Line 1: integer, total final price
Line 2: indices sold at full price (space-separated), or an empty line
Constraints
1 ≤ n ≤ 2*10^5
1 ≤ prices[i] ≤ 10^9
Examples
Input:
5
8 4 6 2 3
Output:
15
3 4
Input:
4
5 1 1 1
Output:
4
1 2 3
Input:
4
1 2 3 4
Output:
10
0 1 2 3
Input:
4
4 3 2 1
Output:
6
3
Input:
1
7
Output:
7
0
Example
Input
5
8 4 6 2 3
Output
15
3 4