/* 

  Candies problem in Picat.

  From HackerRank
  https://www.hackerrank.com/challenges/candies
  """
  Alice is a kindergarden teacher. 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 child.Children get 
  jealous of their immediate neighbors, so if two children sit next 
  to each other then the one with the higher rating must get more 
  candies. Alice wants to save money, so she wants to minimize the 
  total number of candies.
  
  Input
  
  The first line of the input is an integer N, the number of children 
  in Alice's class. Each of the following N lines contains an integer 
  indicates the rating of each child.

  Ouput
  
  Output a single line containing the minimum number of candies Alice must give.
  
  Sample Input
  
  3
  1
  2
  2
  
  Sample Ouput
  
  4
  
  Explanation
  
  The number of candies Alice must give are 1, 2 and 1.
  
  Constraints:
   
  N and the rating  of each child are no larger than 10^5.
  """
  

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  Input = [1,2,2],
  println(input=Input),
  candies(Input,X,Z),
  println(x=X),
  println(z=Z),
  nl.

go2 => 
  N = 1000,
  _ = random2(),
  Input = [1+random() mod ceiling(sqrt(N)) : _ in 1..N],
  println(input=Input),
  candies(Input,X,Z),
  println(x=X),
  println(z=Z),
  nl.

candies(Input, X,Z) =>
   N = Input.length,
   
   X = new_list(N),
   X :: 1..10000,

   Z #= sum(X),

   foreach(I in 2..N) 
     if Input[I-1] > Input[I] then
       X[I-1] #> X[I]
     elseif Input[I-1] < Input[I] then
       X[I-1] #< X[I]
     end
   end,

   solve($[min(Z)], X).