Lemonade Challenge

At a lemonade stand, each lemonade costs Rs.5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a Rs.5, Rs.10, or Rs.20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays Rs.5.

Note that you do not have any change in hand at first.

Given an integer array bills of size n where bills[i] is the bill the ith customer pays, return 1 if you can provide every customer with the correct change, or 0 otherwise.

Input Format

First Parameter: Number n

Second Parameter: An array of numbers bills of size n

Output

Return the number.

Example 1

Input:
5
5 5 5 10 20
Output: 
1
Explanation: 
From the first 3 customers, we collect three Rs. 5 bills in order.
From the fourth customer, we collect a Rs. 10 bill and give back a Rs. 5.
From the fifth customer, we give a Rs. 10 bill and a Rs. 5 bill.
Since all customers got correct change, we output 1.

Example 2

Input: 
5 5 10 10 20
Output: 
0
Explanation: 
From the first two customers in order, we collect two Rs. 5 bills.
For the next two customers in order, we collect a Rs. 10 bill and give back a Rs. 5 bill.
For the last customer, we can not give the change of Rs. 15 back because we only have two Rs. 10 bills.
Since not every customer received the correct change, the answer is 0.

Constraints

• 1 <= n <= 10^5
• bills[i] is either 5, 10, or 20
• Expected Time Complexity - O(n)
• Expected Space Complexity - O(1)