title: candies - interviewstreet
body: <p>Alice is a teacher of kindergarten. She wants to give some candies to the children in her class.  All the children sit in a line and each  of them  has a rating score according to his or her usual performance.  Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.</p>
  
  <h2>Input</h2>
  
  <p>The first line of the input is an integer <code>N</code>, the number of children in Alice's class. Each of the following <code>N</code> lines contains an integer indicates the rating of each child.</p>
  
  <h2>Output</h2>
  
  <p>On the only line of the output print an integer describing the minimum number of candies Alice must give.</p>
  
  <h2>Sample Input</h2>
  
  <pre><code>3
  1
  2
  2
  </code></pre>
  
  <h2>Sample Output</h2>
  
  <pre><code>4
  </code></pre>
  
  <h2>Explanation</h2>
  
  <p>The number of candies Alice must give are 1,2 and 1.</p>
  
  <h2>Constraints:</h2>
  
  <p><code>N</code> and the rating  of each children is no larger than 10^5.</p>
  
  <p>Can anyone please help me?</p>